Phylogenetic relationships among the venomous Australo-Papuan elapid snake radiation remain poorly resolved, despite the application of diverse data sets. To examine phylogenetic relationships among this enigmatic group, portions of the cytochrome b and 16S rRNA mitochondrial DNA genes were sequenced from 19 of the 20 terrestrial Australian genera and 6 of the 7 terrestrial Melanesian genera, plus a sea krait (Laticauda) and a true sea snake (Hydrelaps). These data clarify several significant issues in elapid phylogeny. First, Melanesian elapids form sister groups to Australian species, indicating that the ancestors of the Australian radiation came via Asia, rather than representing a relict Gondwanan radiation. Second, the two major groups of sea snakes (sea kraits and true sea snakes) represent independent invasions of the marine environment. Third, the radiation of viviparous Australian elapids is much older than has been suggested from immunological data. Parsimony analyses were unable to resolve relationships among the Australian radiation, a problem previously encountered with analyses of other (morphological, electrophoretic, karyotypic, immunological) data sets on these species. These data suggest that the reason for this continued difficulty lies in the timing of speciation events: the elapids apparently underwent a spectacular adaptive radiation soon after reaching Australia, such that divergences are ancient even within genera. Indeed, intrageneric divergences are almost as large as intergeneric divergences. Although this timing means that our sequence data cannot fully resolve phylogenetic relationships among the Australian elapids, the data suggest a close relationship of the following clades: Pseudonaja with Oxyuranus; Ogmodon with Toxicocalamus; Demansia with Aspidomorphus; Echiopsis with Denisonia; the "Notechis" lineage with Drysdalia coronoides; and Rhinoplocephalus and Suta with Drysdalia coronata. At least two of the Australian genera (Drysdalia and Simoselaps) appear to be paraphyletic. These sequence data support many of the conclusions reached by earlier studies using other types of data, but additional information will be needed before the phylogeny of the Australian elapids can be fully resolved.