The first fossil assigned to it – a distal right femur piece – was found near the source of the Stono River in Charleston County, South Carolina (United States).

Specimen MCZ 2514, a distal left tarsometatarsus fragment from the Ashley River, was more tentatively assigned to P. mioceanus later on; it was also erroneously believed to be from the Hawthorne Formation.

It was compared to that of Anserinae and Dendrocygninae (other Anseriformes were either similar to these or too unlike P. mioceanus), as well as with Pelecanidae, Phaethontidae and Phalacrocoraciformes[3] of the "higher waterbird" radiation, and found to resemble the former in one, the latter in 4 out of 5 traits.

The thin-walled bone has a second toe trochlea that attaches notably kneewards from the others and is angled slightly outwards while the hallux was vestigial or missing, as is typical for the pseudotooth birds.

Meanwhile, as a presumed pelican relative, P. mioceanus was allied with Cyphornis (another pseudotooth bird, known only from a proximal left tarsometatarsus) and placed in a family Cyphornithidae.

But the enigmatic Late Oligocene Cladornis – the type genus of that supposed suborder – from the Argentinian part of Patagonia is known from a distal right tarsometatarsus only, and thus was not directly comparable to Palaeochenoides and Cyphornis.

And even if Cyphornis is the senior synonym of Palaeochenoides and Tympanoneisiotes (which is not overly likely due to size differences), according to the rules of zoological nomenclature the family name Pelagornithidae would not be affected.