The Cordaitales, an extinct order of plants closely related to the conifers, occupied a wide range of environments during Pennsylvanian times including wetlands, drylands, and uplands. However, claims that some species of cordaitalean grew on marine-influenced coastal margins, and therefore represented the earliest known mangrove communities, have been met with scepticism. Based on new data from the Joggins Formation of Nova Scotia, the ‘cordaitalean mangrove hypothesis’ is reassessed. Small fossil trees in growth position are described from micro-tidal deposits, a sedimentary association inferred to have formed on the margins of a brackish epicontinental sea. The autochthonous trees, which are morphologically different from lycopsid and calamitean trees commonly observed with the Joggins Formation, are probably cordaitalean. This affinity is indicated, in part, by facies-associated parautochthonous remains, which comprise Cordaites leaves, Cordaicladus branches, Cardiocarpus seeds, Cordaianthus reproductive organs, and Dadoxylon wood, a distinctively cordaitalean assemblage. Scour-and-mound structures in beds surrounding the upright trunks show that cordaitalean trees were, at times, submerged in shallow, flowing water. However, Limnopus tetrapod trackways at other horizons demonstrate periodic emergence, indicating that water depths fluctuated in these coastal forests. Analysis of rooting patterns shows that trees persisted through flooding events, despite partial burial by sheets of very fine sandstone and siltstone, survival being facilitated through the development of an adventitious rooting system. However, two key adaptations to growth in marine-influenced soils commonly seen in modern mangrove trees (low shoot:root ratios and small leaves) are not present in the cordaitalean trees. Furthermore, although the trees probably grew in close proximity to the brackish seacoast, direct evidence for marine influence in the fossil forest interval itself is lacking. Consequently, although the cordaitaleans were probably adapted to periodically submerged conditions, and additionally may have tolerated occasional brackish incursions, it is inappropriate to describe them as mangroves in the strict sense.