Using next-generation sequencing technology, we describe the complete mitochondrial genomes for 5 Australian passerine birds (Epthianura albifrons, Petroica phoenicea, Petroica goodenovii, Petroica boodang, and Eopsaltria australis). We successfully assemble each mitogenome de novo using just 1/8th of a Roche GL FSX 454 pyrosequencing plate. From the assembled mitogenomes, we identify 2 different mitochondrial gene arrangements in the region spanning 5'-3' from Cytochrome B to 12s RNA. These gene arrangements represent 2 of the 4 known avian mitochondrial gene arrangements. Our results, together with other previously described avian mitogenomes, highlight that certain mitochondrial rearrangements appear to have arisen multiple times.