Strap-shaped, parallel-veined leaves of Podozamites and Pseudotorellia are among the most common fossils in Late Triassic to Early Cretaceous floras from the Northern Hemisphere. Podozamites is considered to be the leaf of a voltzian conifer, but its cuticle is poorly known, whereas Pseudotorellia, with a thick cuticle and haplocheilic stomata, is commonly considered to be the leaf of a ginkgoalean. Here we describe the leaf morphology, cuticle and stomata of Podozamites and Pseudotorellia based on excellently preserved material from the Early Cretaceous of central Mongolia. Podozamites harrisii sp. nov. has transversely oriented, paracytic (probably syndetocheilic) stomata that are regularly arranged in longitudinal files. Pseudotorellia resinosa sp. nov. and Pseudotorellia palustris sp. nov. have scattered, longitudinally oriented stomata in which the two guard cells are sunken and surrounded by 2-5 specialized lateral subsidiary cells and 1-3 unspecialized polar cells. Association evidence and similarities in cuticular structure suggest that Podozamites harrisii was produced by the same plant as the seed cone Krassilovia. The distinctive stomatal pattern of Podozamites harrisii and Krassilovia is also seen in some species of Swedenborgia and Cycadocarpidium, suggesting these plants may all belong to the same natural group. Cycadocarpidium, Krassilovia and Swedenborgia have previously been treated as conifers, but their transversely oriented, paracytic stomata hint instead at a possible relationship with Bennettitales and Gnetales.