Lycophytes were an important group of plants in the late Permian (Lopingian) vegetation of Southwest China. However, our understanding of these lycophytes is based mostly on the study of megafossil specimens. Here, we describe a unique lycophyte megaspore, Paxillitriletes permicus Sui, McLoughlin et Feng sp. nov., from the Lopingian Xuanwei Formation of Yunnan Province, Southwest China. This trilete megaspore is characterized by prominent membraneous triradiate flanges, long bifurcate spines, an arcuate ridge expanded into a zona, and triangular to polygonal reticulate sculpture. Ultrastructural analysis reveals that the megaspore wall consists of four layers. The innermost layer is the foot layer, which forms a thin and solid basal lamina. It is covered by a dense layer containing small and parallel sporopollenin grains. A thick spongy layer is developed exterior to the dense layer and consists of elongate, curved, and intersected sporopollenin units with porous zones. The outermost layer is dense, of variable thickness, and forms the processes. Morphological and ultrastructural features indicate that the new megaspore belongs to a herbaceous isoetalean. This is the first detailed investigation of megaspores from the Lopingian of China using scanning and transmission electron microscopy. Our discovery represents the oldest occurrence of Paxillitriletes, and adds to the diversity of late Permian lycophytes in the Cathaysian Flora in the paleotropics of the eastern Tethys Ocean.