Coccidia possess three distinct genomes: nuclear, mitochondrial, and plastid. Sequences from five genes located on these three genomes were used to reconstruct the phylogenetic relationships of members of the phylum Apicomplexa: 18S rDNA sequences from the nuclear (nu) genome, partial cytochrome c oxidase subunit I sequences from the mitochondrial (mt) genome, and partial 16S and 23S rDNA sequences and RNA polymerase B sequences from plastid (pl) genomes. Maximum parsimony, maximum likelihood, and Bayesian inference were used in conjunction with nuclear substitution models generated from data subsets in the analyses. Major groups within the Apicomplexa were well supported with the mitochondrial, nuclear, and a combination of mitochondrial, nuclear and concatenated plastid gene sequences. However, the genus Eimeria was paraphyletic in phylogenetic trees based on the nuclear gene. Analyses using the individual genes (18S rDNA and cytochrome c oxidase subunit I) resolved the various apicomplexan groups with high Bayesian posterior probabilities. The multi-gene, multi-genome analyses based on concatenated nu 18S rDNA, pl 16S, pl 23S, pl rPoB, pl rPoB1, and mt COI sequences appeared useful in resolving phylogenetic relationships within the phylum Apicomplexa. Genus-level relationships, or higher, appear best supported by 18S rDNA analyses, and species-level analyses are best investigated using mt COI sequences; for parasites for which both loci are available, nuclear 18S rDNA sequences combined with mitochondrial COI sequences provide a compact and informative molecular dataset for inferring the evolutionary relationships taxa in the Apicomplexa.