Complete nucleotide sequences from the mitochondrial cytochrome b gene (1143 bp) were used to investigate the phylogenetic relationships among the native rodents of Madagascar. Specifically, this study examines whether the nine genera of nesomyines form a monophyletic group relative to other Old World murids. All nine of the nesomyine genera, including multiple individuals from 15 of the 21 described species, were included in the analysis, and their monophyly was assessed relative to the murid subfamilies Mystromyinae, Petromyscinae, Dendromurinae, Cricetomyinae, Murinae, Rhizomyinae, and Calomyscinae. Phylogenetic analysis of the resulting 95 taxa and 540 characters resulted in 502 equally parsimonious cladograms. The strict consensus tree weakly refutes the monophyly of Nesomyinae and suggests that the Malagasy rodents form a clade with dendromurines (as represented by Steatomys) and the African rhizomyine Tachyoryctes. The cladogram strongly refutes the association of the South African genus Mystromys with the Malagasy genera and suggests that Petromyscus and Mystromys form a monophyletic group. We provide the first explicitly phylogenetic scenario for the biogeographic history of nesomyine rodents. Our phylogenetic hypothesis indicates: (1) rodents invaded Madagascar only once, (2) they came from Asia not from Africa as is commonly assumed, and (3) there was a secondary invasion of rodents from Madagascar into Africa.