C4 photosynthesis is a complex evolutionary trait which evolved independently over 60 times. To study the mechanisms of how the C4 pathway evolved with such repeatability, it is useful to employ a comparative approach where its evolutionary acquisition by distinct lineages is evaluated. Genera known to have both C3 and C4 species and species with intermediate character states are prime candidates for comparative studies of C4 evolution. In this study, we characterize the physiology of C3-C4 intermediate species in Tribulus which are prostrate herbs of hot, semi-arid habitats of low-to-mid latitude. We grew ten Tribulus species under common conditions in growth chambers and examined leaf gas exchange, enzyme activity, and ultrastructure. C3-C4 intermediacy in this genus occurs in two species: T. cristatus and T. astrocarpus. Tribulus cristatus is a typical C3-C4 intermediate using C2 photosynthesis, a physiology where photorespiratory glycine is shuttled into the bundle sheath. Tribulus astrocarpus exhibited traits characteristic of an early phase of C4 evolution termed proto-Kranz, as demonstrated by localization of mitochondria and chloroplasts to the centripetal (interior) region of the bundle sheath cells in the leaves. T. astrocarpus had a slight reduction of photosynthetic CO2 compensation point, but we did not detect localization of glycine carboxylase to the bundle sheath. Other C3 species exhibited varying degrees of organelle enrichment and localization in the bundle sheath cells. The proto-Kranz character state has only been identified in a few lineages of C4 photosynthesis (notably Steinchisma, Euploca and Flaveria). With the addition of T. astrocarpus, we provide key evidence that the proto-Kranz character state is a common initial step in C4 photosynthetic evolution.