Of the four species, two (P. gunnari and P. klekowskii) are known from numerous remains found in Middle or Late Eocene strata (34 to 50 MYA) of the La Meseta Formation on Seymour Island, Antarctica. P. antarcticus, the first fossil penguin described, is only really known from a single incomplete tarsometatarsus found in the Late Oligocene Otekaike Limestone (23 to 28, possibly up to 34 MYA) at Kakanui, New Zealand, but numerous other bones have been tentatively assigned to the species. The other described New Zealand species, P. marplesi, is known from parts of a skeleton, mainly leg bones, from the Middle or Late Eocene Burnside Mudstone (34 to 40 MYA) at Burnside, Dunedin. To this species also a number of additional remains have been tentatively assigned. The problem with the indeterminate New Zealand specimens is that they at least in part are intermediate in size between the two species (Simpson, 1971). It may be that P. marplesi simply evolved into the smaller P. antarcticus. Bones unassignable to species also were found on Seymour Island, but in these cases they seem to be from juvenile individuals or are simply too damaged to be of diagnostic value (Jadwiszczak, 2006).
In addition, an incomplete right tibiotarsus (South Australian Museum P10862) and one left humerus (South Australian Museum P7158) and assignable to this genus were found in the Late Eocene Blanche Point Marls at Witton Bluff near Adelaide, Australia (Simpson, 1946, 1971). Additionally, an incomplete humerus identified as Palaeeudyptes was recovered in southernmost Chile (Sallaberry et al., 2010), from middle to late Eocene beds of the Río Turbio Formation, near Puerto Natales, 200 km south from Torres del Paine National Park.
The supposed genus Wimanornis, based on two Seymour Island humeri, is apparently a synonym of P. gunnari (Jadwiszcak, 2006).
The genus is the namesake for the subfamily of primitive penguins, Palaeeudyptinae. Altogether, their osteological characteristics seem to have been somewhat less advanced that those of the slightly smaller Archaeospheniscus and about on par with the gigantic Anthropornis. The exact nature of the relationship of the Palaeeudyptinae to modern penguins is unknown.