Palaelodus was most abundant during the Late Oligocene to Middle Miocene periods, but isolated remains from Australia indicate that the genus, or at least a relative, survived until the Pleistocene.

The genus Palaelodus was first described by French scientist Alphonse Milne-Edwards in 1863 on the basis of fossils discovered in France's early Miocene deposits of the Saint-Gérand-le-Puy area.

In 1933 P. minutus was sunk into P. gracilipes by Lambrecht, a decision not immediately followed by other paleontologists like Brodkorb or Švec, but later accepted by Jacques Cheneval in 1983 during a major revision of the palaelodids of Saint-Gérand-le-Puy.

[4] Palaelodus remains were first recognized in Australia in 1982, but not described until 1998 when Baird and Vickers-Rich erected two new species, P. wilsoni and P. pledgei, based on fossils from the Lake Eyre Basin.

[4] The pedal phalanges, the bones that make up the middle toes, of Palaelodus are compressed mediolaterally unlike those of flamingos, deep and with weakly developed convex distal articulation points that lack a furrow.

Although this is also true for grebes to some extant, podicipediforms show dorsoventrally flattened toes, indicating that this is not an ancestral trait and was instead acquired independently in both lineages.

The ungual phalanges could not be described by Mayr in his detailed analysis of Palaelodus material, however he notes that older figures seem to indicate that the toe tips were not flattened like in grebes or flamingos and instead show the state typical for other bird groups.

Palaeolodids such as Palaelodus are considered to be an important link in understanding the relationship between flamingos and their next closest relatives, the diving grebes with which they from the clade Mirandornithes.

This relationship is well supported by both molecular and morphological evidence and the Palaelodidae form a link between the two extant groups with cranial anatomy and general proportions similar to flamingos but legs akin to those of grebes.

[11] † Juncitarsus Podicipediformes † Palaelodidae †Harrisonavis Phoenicopterus Phoenicoparrus Due to its unique anatomy and intermediary position within mirandornithes, the exact ecology of Palaelodus is not entirely understood.

[4] Cheneval and Escuillié proposed that the deep mandible of Palaelodus may have housed an enlarged tongue similar to that of flamingos and that these birds may have shown the first signs of becoming filter feeders.

Although not directly disputing the presence of an enlarged tongue, Mayr points out that the bill of Palaelodus lacked the widened rim that holds the keratinous lamellae that allow flamingos to filter water.

Furthermore, the enlarged fossae on the sides of the mandibular ramus indicate that movement of the head played a greater role in foraging than it does for flamingos, pointing to a more conventional method of feeding.

[4] Fossils of Palaelodus are exclusively known from lacustrine environments and the presence of salt glands indicates that regardless of the details of their diet, they must have foraged in saline or at least brackish waters like flamingos.

The large number of Palaelodus remains found in certain localities indicates that areas inhabited by this genus were rich in their favored food items.

Worthy and colleagues argue that the discovery of thousands of bones in France could indicate that the European Palaelodus species may have lived in large flocks like modern flamingos.

The avifauna of this lake was dominated by anseriforms, but also featured other birds associated with bodies of water like wading birs, cranes, rails, tubenoses, herons and gulls.