Two brackish water tongues of the Cannonball Formation (Fort Union Group) are exposed in badlands of the Little Missouri River in southwestern North Dakota. These brackish water deposits are intercalated with lignite-bearing, fluviolacustrine rocks of the Ludlow and Slope Formations (Fort Union Group) and, in total, represent a fluviodeltaic complex that prograded eastward into the Paleocene Cannonball Sea. The invertebrate fauna, lithology, and vertical lithologic sequences indicate that lacustrine, coal swamp, interdistributary bay or interlobe basin, and lake or bay fill depositional environments are represented by the brackish water deposits; the sub- and superjacent strata are of freshwater origin. Cluster analysis and ordination statistical techniques demonstrate that paleoenvironment is a factor that exerted control on the taxonomic composition of palynomorph assemblages. In general, brackish water deposits are characterized by rare-to-abundant dinoflagellate cysts. Differences among assemblages within brackish water deposits appear to be related to salinity and the rate of clastic influx. Slightly brackish to fresh water deposits that received low clastic input are characterized by abundant freshwater algae, low diversity of dinoflagellate cysts, and few terrestrial palynomorphs. Brackish water deposits receiving high clastic input are characterized by abundant terrestrial palynomorphs and more diverse dinoflagellate assemblages. Lacustrine environments that had high clastic influx are dominated by terrestrial palynomorphs. Palynomorph assemblages recovered from coal swamp environments are variable, possibly reflecting localized plant communities. The rare presence of dinoflagellate cysts within the lignites suggests marine influence during peat deposition.