Palaeoaplysina is an enigmatic platy macrofossil with a cellular skeleton and internal canal system common to upper Carboniferous–lower Permian reefs of the northern hemisphere. Its rapid flourishing from the Moscovian and subsequent extinction near the end of the Sakmarian, as well as its unique combination of physical features, are poorly understood. In addition to Palaeoaplysina reefs forming major petroleum exploration targets in Russia, Palaeoaplysina is abundant and well preserved in the Sverdrup Basin in the Canadian Arctic Archipelago. A new genus of Palaeoaplysinaceae, Eopalaeoaplysina n. gen., is also widespread in the Sverdrup Basin and identified based on a simple morphology with broad canals distributed in roughly even rows. The distribution of paleoaplysinids in strata from the Moscovian to the Sakmarian in the Sverdrup Basin reveals Eopalaeoaplysina and Palaeoaplysina represent two distinct reef-building forms with an increase in complexity over time. The aragonitic composition of Palaeoaplysina, in addition to its distribution within the photic zone and differentiated cellular skeleton, suggests paleoaplysinids were ancestral red algae. Palaeoaplysina occurs in both low-energy back-reef and higher-energy reef front facies. Preserved thin edges of Palaeoaplysina plates indicate it was encrusting, at least in low-energy conditions. The exclusion of Palaeoaplysina from the late Paleozoic tropics and the southern hemisphere, its rapid appearance and proliferation, and its eventual extinction may point towards an evolutionary niche optimized for warm-water conditions at unusually high latitudes along the western margin of Pangea.