Phoeniconaias proeses was first described by Charles Walter De Vis in 1905 alongside a variety of other fossil birds. At the time De Vis was under the impression that the material, a left distal tarsometatarsus only described to have been found in the Lake Eyre basin without precise locality or age, belonged to a type of shorebird. Rich and colleagues argue that this identification may have been a result of De Vis' limited reference collection, which did not include bones of flamingos. Subsequently, De Vis was incapable of comparing his material with extant flamingos and instead had to assign it to the most similar group available to him. The material, named Ocyplanus proeses by De Vis, was then placed in the family Laridae by Lambrecht in 1933, an assignment then supported by Pierce Brodkorb in 1967. Around the same time Miller named the first recognized flamingo fossils from Australia, erecting several species including Phoeniconaias gracilis from Lake Kanunka in the Lake Eyre basin.^[1] In 1975 Condon proposed that Ocyplanus proeses was not a shorebird at all and instead represented a type of rail. In 1987, Rich and colleagues examined the material and determined that the description and size of O. proeses matches Miller's diagnosis for Phoeniconaias gracilis, rendering the later a synonym of De Vis' taxon. In the same publication the authors examine Ibis (?) conditus, also named by De Vis in 1905 based on a femur from Wurdulumankula and placed in Threskiornithidae. The team argues that the femur, stouter than in ibises, more closely resembles flamingos and also assign it to Ocyplanus proeses, which is of similar size.^[2] Although the name Ocyplanus was initially kept due to the differences in the tibiotarsus and femur distinguishing it from the modern lesser flamingo, the combination Phoeniconaias proeses was used in later publications due to the fact that the name Ocyplanus is occupied by a beetle.^[3]

Based on the surface texture of the fossil, the holotype of Phoeniconaias proeses is thought to have belonged to a juvenile approximately the size of a beach stone-curlew. According to Rich et al., this fossil matches the diagnosis given by Miller for Phoeniconaias gracilis. This diagnosis included that the tarsometatarus was smaller and more slender than the corresponding bone in the lesser flamingo. The posterior extension of the second trochlea is not as rounded and on the plantar surface of the fourth trochlea the articular surface does not extend as far back. The additional material identified by Miller generally matches the corresponding bones in the extant Phoeniconaias species.^[1] Rich and colleagues however do point out that the features of the trochlea are very variable in extant genera, before agreeing that the mediolateral compression of the species most closely resembles the lesser flamingo out of all modern genera. They also add that certain features of the referred material serve as additional differentiation from modern flamingos. This includes the placement of the ligamental groove, the flattened state of the distal end and the sloping of the condyles.^[2]

The femur originally named Ibis (?) conditus shows the stout morphology typical for flamingos as well as sharply curved line near the popliteal fossa. However, unlike Miller's tarsometatarus which is incredibly similar to Phoeniconaias, this element shows several differences that clearly set it apart from all modern flamingos. For instance, the intermuscular line remains straight over most the femur's length until it makes a drastic concave turn to contact the trochanter. The front of the shaft is deeply excavated in the proximal region and lacks a foramen that in other flamingos aids with skeletal pneumaticity. The pit for the ligament at the fibular condyle is deep, proximal to which lie a prominent ridge and well defined channel. The ridge is only weakly present in modern flamingos and the well defined channel absent.^[2]

Both Miller and Rich et al. describe Phoeniconaias proeses as being among the smallest known flamingo, fossil or otherwise. The type material of P. proeses is clearly smaller than the same bone in the extant lesser flamingo. The femur described by De Vis is also smaller than in modern Phoeniconaias and subsequently matches what was described for P. proeses. Miller writes that it's approximately 10% smaller than the smallest individuals of the lesser flamingo and also smaller than the small American forms Phoenicopterus minutus and Phoenicopterus stocki. Due to this Miller argues that P. proeses, at least based on the Lake Kanunka material, was the smallest known flamingo in the fossil record. Rich and colleagues, who worked with more material of the species, disagree with this, stating that Leakeyornis from Miocene Kenya was even smaller.^[2] Miller did identify a humerus that in size would match the modern lesser flamingo, but also notes that this fossil would not only fall within the range of variation for P. proeses, but might also be deceptive, as the wings may not reflect the small and gracile build of the rest of the body.^[1]

Material assigned to Phoeniconaias proeses is known from various localities in Australia. During the Pliocene at Lake Kanunka it coexisted with at least two other species of flamingo, the large greater flamingo and Xenorhynchopsis minor, which is approximately the size of the lesser flamingo. It was again found alongside greater flamingos at Wurdulumankula, Lower Wolf Creek, though the precise age of that site is unknown. Although it is unknown when precisely Phoeniconaias proeses went extinct, flamingos as a whole disappeared from Australia during the Quaternary, when increasing aridification destroyed the shallow lakes these birds require to feed and nest.^[1][2]