Nucleotide and amino acid sequence data from the mitochondrial cytochrome b (Cytb) and cytochrome c oxidase subunit I (COI) gene segments were used to gain insights into the population biology and phylogenetic relationships of two species of hematophagous kissing bugs (Hemiptera: Reduviidae: Triatominae) from the Sonoran Desert of northwestern Mexico and southern Arizona, USA, Triatoma rubida (Uhler, 1894) and T. recurva (Stål, 1868), both of which are vectors of the protozoan parasite Trypanosoma cruzi responsible for Chagas' disease. Analysis of molecular variance of gene sequences indicated significant structure among populations of both species from widely separated geographic localities. Phylogenetic analyses of gene and amino acid sequences employing both Bayesian and parsimony methods showed that T. recurva clustered within the phyllosoma complex of Triatoma species from central and southern Mexico with high statistical support, and that it was closely related to T. longipennis. Triatoma dimidiata also was shown to be closely related to the phyllosoma complex, as was T. sanguisuga which has historically been assigned to the lecticularia complex. Analyses of gene sequences were unable to confidently resolve relationships of T. rubida, although weak support for a T. nitida+T. rubida clade was seen under certain conditions. A provisional calibration of a mitochondrial DNA molecular clock for T. rubida, based on geological dates for the vicariant separation of the Baja California peninsula from mainland Mexico, suggested that pairwise sequence divergences for the Cytb and COI genes were 1.1-1.8% and 0.6-1.0% per million years, respectively. Two highly supported sympatric lineages of T. rubida uhleri from southern Arizona, which are hypothesized to have diverged approximately 550,000-900,000 years ago, were detected in the Cytb gene trees.