C(4) photosynthesis involves alterations to the biochemistry, cell biology, and development of leaves. Together, these modifications increase the efficiency of photosynthesis, and despite the apparent complexity of the pathway, it has evolved at least 45 times independently within the angiosperms. To provide insight into the extent to which gene expression is altered between C(3) and C(4) leaves, and to identify candidates associated with the C(4) pathway, we used massively parallel mRNA sequencing of closely related C(3) (Cleome spinosa) and C(4) (Cleome gynandra) species. Gene annotation was facilitated by the phylogenetic proximity of Cleome and Arabidopsis (Arabidopsis thaliana). Up to 603 transcripts differ in abundance between these C(3) and C(4) leaves. These include 17 transcription factors, putative transport proteins, as well as genes that in Arabidopsis are implicated in chloroplast movement and expansion, plasmodesmatal connectivity, and cell wall modification. These are all characteristics known to alter in a C(4) leaf but that previously had remained undefined at the molecular level. We also document large shifts in overall transcription profiles for selected functional classes. Our approach defines the extent to which transcript abundance in these C(3) and C(4) leaves differs, provides a blueprint for the NAD-malic enzyme C(4) pathway operating in a dicotyledon, and furthermore identifies potential regulators. We anticipate that comparative transcriptomics of closely related species will provide deep insight into the evolution of other complex traits.