The family, Palaelodidae, is the sister taxon of modern flamingos, and the order Phoenicopteriformes, to which both belong, probably evolved from a grebe-like ancestor. It is easy to see how a bird like Palaelodus represents an intermediate form between a diving, fish-eating grebe and a wading, invertebrate-filtering flamingo. This does not mean that the palaelodids are the ancestors of the flamingos. Rather, they were a sister group that remained in the ecological niche of their common ancestor.
The number of species in the genus is disputed. The species P. ambiguus was found in Middle Oligocene to Middle Miocene (c. 29-12 mya) deposits of Western and Central Europe, being rare in Oligocene and much more common in Miocene strata (Hugueney et al., 2003). The Romanian fossil Grus miocaenicus is sometimes considered a synonym of this species. Other, somewhat doubtful species described from the Late Oligocene to Early Miocene (c. 28-23 mya) of French inland sites are P. gracilipes and P. crassipes which are most common in the Late Oligocene and later are replaced by P. ambiguus (Hugueney et al., 2003).
From Late Oligocene to Middle Miocene (c. 28-12 mya) sites in Australia, two species, P. pledgei and P. wilsoni have been described. The latter was also claimed from Middle Pleistocene deposits (roughly half a million years ago) in Australia; given the large temporal gap, it might not belong to the genus. On the other hand, the supposed crane Pliogrus germanicus is most likely a palaelodid. Sometimes Megapaloelodus goliath is included in Palaelodus.