Background: Debate regarding the monophyly and relationships of the avian order Pelecaniformes represents a classic example of discord between morphological and molecular estimates of phylogeny. This lack of consensus hampers interpretation of the group's fossil record, which has major implications for understanding patterns of character evolution (e.g., the evolution of wing-propelled diving) and temporal diversification (e.g., the origins of modern families). Relationships of the Pelecaniformes were inferred through parsimony analyses of an osteological dataset encompassing 59 taxa and 464 characters. The relationships of the Plotopteridae, an extinct family of wing-propelled divers, and several other fossil pelecaniforms (Limnofregata, Prophaethon, Lithoptila, ?Borvocarbo stoeffelensis) were also assessed. The antiquity of these taxa and their purported status as stem members of extant families makes them valuable for studies of higher-level avian diversification.

Methodology/Principal Findings: Pelecaniform monophyly is not recovered, with Phaethontidae recovered as distantly related to all other pelecaniforms, which are supported as a monophyletic Steganopodes. Some anatomical partitions of the dataset possess different phylogenetic signals, and partitioned analyses reveal that these discrepancies are localized outside of Steganopodes, and primarily due to a few labile taxa. The Plotopteridae are recovered as the sister taxon to Phalacrocoracoidea, and the relationships of other fossil pelecaniforms representing key calibration points are well supported, including Limnofregata (sister taxon to Fregatidae), Prophaethon and Lithoptila (successive sister taxa to Phaethontidae), and ?Borvocarbo stoeffelensis (sister taxon to Phalacrocoracidae). These relationships are invariant when ‘backbone’ constraints based on recent avian phylogenies are imposed.

Conclusions/Significance: Relationships of extant pelecaniforms inferred from morphology are more congruent with molecular phylogenies than previously assumed, though notable conflicts remain. The phylogenetic position of the Plotopteridae implies that wing-propelled diving evolved independently in plotopterids and penguins, representing a remarkable case of convergent evolution. Despite robust support for the placement of fossil taxa representing key calibration points, the successive outgroup relationships of several “stem fossil + crown family” clades are variable and poorly supported across recent studies of avian phylogeny. Thus, the impact these fossils have on inferred patterns of temporal diversification depends heavily on the resolution of deep nodes in avian phylogeny.