Similar to Phiomia, its nasal cavity was retracted and surrounded by strong muscle attachment sites, indicating that it was among the first proboscideans to possess a trunk.

[3][4] It was described in 1901 by British palaeontologist Charles William Andrews, who named its type species, P. beadnelli, after his colleague, Hugh John Llewellyn Beadnell.

[8][9] Writing in 1926, Henry Fairfield Osborn suggested that Palaeomastodon was a direct, if remote, ancestor of gomphotheres and mammutids (which he referred to under the umbrella of "mastodonts").

[10] In a 1988 paper discussing the taxonomy of proboscideans, Pascal Tassy suggested that Palaeomastodon fell under the suborder Elephantiformes, being phylogenetically closer to modern elephants than to taxa like Deinotherium and Moeritherium, though was still more basal than Phiomia.

However, based on the reported 87.5 cm (34.4 in) length of one femur, a 2016 study estimated an adult shoulder height of 2.2 m (7 ft 3 in), and a body mass of over 2,500 kg (5,500 lb).

[1] The mandibular symphysis is extremely elongated,[14][15] with a dorsal surface that bears a deep and wide supra-symphyseal groove, indicating that Palaeomastodon possessed a long tongue.

[17] The environment of the Jebel Qatrani Formation, from which Palaeomastodon is known, has been described as a subtropical to tropical lowland plain by Bown, who further suggests the presence of streams and ponds.

[18] Based on the occurrence of birds that are associated with water (such as ospreys, early flamingos, jacanas, herons, storks, cormorants and shoebills), Rasmussen and colleagues inferred that the environment featured slow-moving freshwater with a substantial amount of aquatic vegetation, which matches the prior hypothesis.

Although lithology suggests that most fossils were deposited on sandbanks after being transported by currents, the authors argue that swamps could have easily formed along the banks of the river that was present during the Oligocene and may account for the mudstone found in certain quarries.

The absence of other birds typical for such an environment may be explained either through sampling bias or due to the fact that said groups had simply not yet been present in Oligocene Africa.

[19] The discovery of snakehead fossils seem to support Rasmussen's interpretation, as the genus Parachanna today prefers slow-moving backwaters with plenty of vegetation.

[20] In a 2001 paper Rasmussen et al. argued that the sandstone and mudstone of the formation likely formed as sediments were aggraded by a system of river channels that emptied towards the west into the Tethys.

[21] Overall this indicates that this region was a part of an extensive belt of tropical forest that stretched across what is now northern Africa, which would gradually give rise to open woodland and even steppe the further one was to travel inland.