The fossilized parts of several plants are described from the Lower Cretaceous of the Serra do Tucano Formation, Brazil. These include ovulate cones with whorls/decussate bracts involving one terminal female reproductive unit sometimes attached to an incomplete shoot with striated axes and nodes with unequivocal ephedroid affinity. A new genus, Paraephedra, is proposed to accommodate three different ovulate structures. Paraephedra amazonensis is interpreted as a terminally attached single ovule/seed surrounded by whorls/decussate bracts that cover the ovule almost completely. Paraephedra sp. 1 is interpreted as a single ovoid to elongate-ovoid ovule/seed surrounded by one to two connate bracts extending to just below the middle of the ovule. Paraephedra sp. 2 is interpreted as a terminally attached single ovule/seed surrounded by one to two pairs of decussate bracts that cover the ovule almost completely. Although the general morphology of Paraephedra bears a strong resemblance to Ephedra L., the expected micropylar tube is missing (or has not been confirmed), thus preventing its classification in the Ephedrales/Ephedraceae. The association of these Ephedra-like reproductive structures with other taxa previously recognized from the Serra do Tucano Formation support the hypothesis that the Takutu Basin region was under an arid/semi-arid climate regime during the Barremian-Albian interval.