Molecular phylogenetics has revolutionized our understanding of the Caryophyllales, and yet many relationships have remained uncertain, particularly at deeper levels. We have performed parsimony and maximum likelihood analyses on separate and combined data sets comprising nine plastid genes (similar to 12,000 bp), two nuclear genes (similar to 5000 bp), and the plastid inverted repeat (similar to 24,000 bp), giving a combined analyzed length of 42,006 bp for 36 species of Caryophyllales and four outgroups. We have recovered strong support for deep-level relationships across the order. Two major subclades are well supported, the noncore and core Caryophyllales; Rhabdodendron followed by Simmondsia are sisters to the core Caryophyllales, Limeum and Stegnosperma are successive sisters to the "globular inclusion'' clade, Gisekia is a distinct lineage well separated from Rivina within the "raphide'' clade, and Rivina and Phytolaccaceae are disparate lineages, with Rivina sister to Nyctaginaceae. The placement of Sarcobatus and relationships within the portulacaceous cohort remain problematic. Within the latter, Halophytum is sister to Basellaceae and Didiereaceae, and the clade comprising Portulaca, Talinum, and Cactaceae is well supported. Classical hypotheses argued that the early Caryophyllales had evolved in open, dry, marginal environments at a time when pollinators were scarce, and, as such, the ancestral caryophyllid flower was wind pollinated with an undifferentiated perianth. We reevaluated these hypotheses in light of our phylogeny and find little support for anemophily as the ancestral condition; however, the early caryophyllid flower is suggested to have possessed an undifferentiated perianth. A subsequent minimum of nine origins of differentiated perianth is inferred. We discuss the evidence for independent origins of differentiated perianth and highlight the research opportunities that this pattern offers to the field of evolutionary developmental genetics.