The excellent penguin fossil record is temporally long, among the oldest of modern birds, and contains fossils on every Gondwanan continent except India. However, most of fifty-nine named taxa are isolated skeletal elements, many of which are noncomparable. Fossil diversity is highest in New Zealand, with additional Antarctic and Patagonian faunas and fewer remains from Australia and South Africa. Phylogenetic hypotheses place penguins within Aves and Neornithes, but further relationships remain contentious. Recent work clarified living species' phylogeny, but none examined all fossil taxa. I describe penguin skeletal anatomy using CT scans and museum specimens, providing the first such description for all living and extinct species in an explicitly phylogenetic framework. All elements are phylogenetically variable, intergeneric variation is large, and extinct taxa are more variable than extant. I recommend that future systematic works include all elements for extinct species diagnoses, osteology for living species, and discussions of intraspecific variation. This description grounds my phylogenetic analysis, based on a 503-character matrix of osteological, myological, integumentary, and behavioral characters. This greatly expands previous datasets, and allows recovery of a highly resolved phylogeny, including monophyly of two extinct clades and the crown-group. Data partitions support different levels of relationship, whereas missing data and outgroup choice drastically affect recovered topology. Incorporating the maximum amount of data gives the highest resolution by recovering all relevant character states. I propose the first formal phylogenetic nomenclature for sphenisciforms, and define and diagnose previously used terms such as Panspheniscidae (total group), Sphenisciformes (known penguins), Spheniscidae (crown-group), Palaeeudyptidae and Paraptenodytidae (two extinct clades). I coin Spheniscoidea (Spheniscidae + Paraptenodytidae) and Australodyptinae (Aptenodytes + Pygoscelis). After calibration with geologic time, I calculate the completeness of the pencuin record and determine confidence intervals to estimate a Cretaceous origin and an Eocene crown-clade origin. These dates and the derived phylogenetic placement of penguins suggest that numerous extant bird lineages may also have Cretaceous origins. I recover a New Zealand origin for penguins and a West Antarctic origin for the crown-group and extinct clades. Correlating penguins with tectonic and climatic data indicates an Eocene adaptive radiation, probably related to latest-stage Gondwanan breakup and associated global cooling.