This study involves bryophyte fossils from the Teresina Formation (Permian–Guadalupian) collected in the Rio Preto Quarry in the state of Paraná, southern Brazil. Two new genera are proposed, with two new species: Capimirinus riopretensis sp. nov. and Yguajemanus yucapirus sp. nov. C. riopretensis sp. nov. included a lateral sporophyte that was organically attached to a gametophyte and is thus one of the oldest pleurocarpous fossils known today. This discovery provides clear evidence of the evolution of mosses during the Permian, because an acrocarpous moss from this period was also found in India. The preservation of such a fragile structure demonstrates that no prefossilization displacement took place and that the sediments accumulated in a low-energy, fresh-water environment, similar to a lake fed by rain, and isolated from the direct influence of the sea. Campimirinus riopretensis may be placed within the earlier pleurocarps, and Yguajemanus yucapirus sp. nov. may belong to the Bryalean families. However, we were not able to place neither of these species in any existing family today.