The evolutionary origin of the pinnipeds (seals, sea lions, and walruses) is still uncertain. Most authors support a hypothesis of a monophyletic origin of the pinnipeds from a caniform carnivore. A minority view suggests a diphyletic origin with true seals being related to the mustelids (otters and ferrets). The phylogenetic relationships of the walrus to other pinniped and carnivore families are also still particularly problematic. Here we examined the relative support for mono- and diphyletic hypotheses using DNA sequence data from the mitochondrial small subunit (12S) rRNA and cytochrome b genes. We first analyzed a small group of taxa representing the three pinniped families (Phocidae, Otariidae, and Odobenidae) and caniform carnivore families thought to be related to them. We inferred phylogenetic reconstructions from DNA sequence data using standard parsimony and neighbor-joining algorithms for phylogenetic inference as well as a new method called spectral analysis (Hendy and Penny) in which phylogenetic information is displayed independently of any selected tree. We identified and compensated for potential sources of error known to lead to selection of incorrect phylogenetic trees. These include sampling error, unequal evolutionary rates on lineages, unequal nucleotide composition among lineages, unequal rates of change at different sites, and inappropriate tree selection criteria. To correct for these errors, we performed additional transformations of the observed substitution patterns in the sequence data, applied more stringent structural constraints to the analyses, and included several additional taxa to help resolve long, unbranched lineages in the tree. We find that there is strong support for a monophyletic origin of the pinnipeds from within the caniform carnivores, close to the bear/raccoon/panda radiation. Evidence for a diphyletic origin was very weak and can be partially attributed to unequal nucleotide compositions among the taxa analyzed. Subsequently, there is slightly more evidence for grouping the walrus with the eared seals versus the true seals. A more conservative interpretation, however, is that the walrus is an early, but not the first, independent divergence from the common pinniped ancestor.