The bony-toothed or pseudotooth birds were initially believed to be related to albatrosses in the Procellariiformes, but actually they seem to be rather close relatives of either pelicans and storks, or of waterfowl, and are here placed in the order Odontopterygiformes to account for this uncertainty. Also, their internal taxonomy is not well-resolved. An earlier-described pseudotooth bird, Cyphornis magnus from Vancouver Island (Canada), was believed to be of Eocene age but is nowadays assumed to have lived in the Early Miocene, not too long before the Clarendonian (Middle/Late Miocene) O. orri. It may be that Osteodontornis is a junior synonym of Cyphornis.
With a wingspan of 5.5 to 6 metres (18 to 20 ft) and a height of 1.2 metres (3.9 ft) when on the ground, Osteodontornis orri and similar giant pseudotooth birds were the second-largest flying birds known, surpassed only by the teratorn Argentavis magnificens. The head, from neck to bill-tip, measured about 40 centimetres (1.3 ft), and the eyesockets were about 5.3 centimetres (2.1 in) wide. The humerus, though about as long as a human's, was only about 3.5 centimetres (1.4 in) wide at the shoulder end. The skull's quadrate bone measured almost 30 millimetres (1.2 in) at its widest and was nearly 45 millimetres (1.8 in) high.
Like its relatives, O. orri had a stout but extremely light-boned body, feet that were presumably webbed as in its aquatic relatives, and long and probably very narrow wings resembling those of an albatross. Its beak made up about three-quarters of the head's length and had bony tooth-like serrations that were hollow or maybe filled with cancellous bone. The beak was so heavy the creature probably held it between its shoulders while in flight, just like modern pelicans do. The arrangement of its bony serrations is characteristic for this genus: one small "tooth", flanked by small points or even smaller "teeth", is placed between each pair of large ones. However, the "tooth" pattern of pseudotooth birds changed along the length of the beak, and is not considered a very reliable way to distinguish genera.
In general lifestyle, it was probably most similar to the albatrosses, tropicbirds and frigatebirds of today, with long slender wings adapted for soaring vast distances over the open seas. Due to its size, the bird is presumed to have been an excellently adapted dynamic soarer. It probably built its nest on high plateaus or similar places, where it could easily take flight by simply walking into the wind with wings spread. It was a seabird that apparently lived mainly off squid and other soft-bodied prey; the "teeth" were less saw-like than the horny serrations on the beak of the fish-eating saw-billed ducks (Merginae), pointing straight downwards instead and in the fossils often very abraded or broken. The downward-pointing "teeth" were ideal for digging into and holding slippery, soft-skinned pelagic animals such as cephalopods that were probably snatched out of the water in flight or while swimming. Lightly built as it was, O. orri was probably not a good diver and may have found it impossible to dive at all.
Osteodontornis is one of the pseudotooth birds of which rather comprehensive remains are known, but the lack of good fossils of most other Odontopterygiformes allows for few direct comparisons between genera. Still, the distal humerus of the present genus (e.g. the Barstovian specimen LACM 50660 from Kern County, California) can be compared to that of a smaller and older fossil tentatively assigned to Odontopteryx. Osteodontornis has a wider and deeper notch between the external condyle and the ectepicondylar prominence, with the pit between these farther from the bone's end, than did the smallish Paleogene species. Its quadrate bone differed from that of Odontopteryx toliapica in a more narrowly grooved dorsal head, and a larger and less forward-pointing orbital process. The forward center of the ventral articulation ridge extends upwards and forward, and the pterygoid process is conspicuously expanded to the upper center in Osteodontornis. The socket for the quadratojugal has an intermediate position and the lateral ridge of the slender main shaft is straight and fairly thin. The quadrate of the mysterious Pseudodontornis longirostris skull (which some consider to belong in Pelagornis) is not very well preserved; it agees with Odontopteryx in a broad main shaft and with Osteodontornis in the straight main shaft ridge and its upward-directed ventral articulation ridge's forward center. Otherwise, it differs from both.
This species is well documented from various locations of generally Miocene age, although usually by much fragmented remains due to the thin and tender bones it had. Most importantly, it was found on both sides of the North Pacific. It is not certain whether all Osteodontornis remains belong to a single species; size differences suggest that some evolution took place during the timespan in which the genus existed. Thus, some fossils are referred to Osteodontornis only, without further assigning them to this species.
The type specimen of O. orri, SBMNH 309, is a rather comprehensive fossil preserved mostly as imprint, with some bone pieces and even feather impressions in addition; it was found in Clarendonian (Late Miocene) shale of California (USA). Subsequently, for example in the Barstovian (Middle Miocene) Round Mountain Silt or in Late Miocene deposits of the Monterey Formation, quite a few additional specimens dating from about the same time were found in California. Roughly contemporary specimens were described from the Haranoyan-Tozawan boundary in Japan – a complete right quadrate bone (NSM PV-18696) from the Middle Miocene Nagura Formation at Chichibu, Saitama, an Early Miocene right mandible piece (MFM 28351) found in the Oi Formation at Misato, Mie, and some additional material of about the same age from the Mizunami Group at Mizunami, Gifu. From the Early Miocene Nye Formation and the Middle Miocene Astoria Formations of Oregon a handful of specimens that appear to be Osteodontornis are known. Similar fossils have been found in the Middle Miocene Capadare Formation of Venezuela and from the Late Miocene of the Pisco Formation of Peru; they might rather be of a distinct but closely related genus, and it must be remembered that at that their time the Isthmus of Panama had not been formed yet so that an affiliation with the Atlantic Pelagornis cannot be discounted. The former, specimen MBLUZ-P-5093 from Cueva del Zumbador in Falcón State, is a premaxilla tip of immense dimensions; its bearer might have exceeded a wingspan of 7 metres (23 ft) in life. Though some of the Miocene North American material was initially (and sometimes is still) assigned to Pelagornis, recent authors generally place them in the present genus. 
Some wing bone fossils from the Eo-Oligocene boundary of Oregon (USA), though assigned to Argillornis (= Dasornis), do not differ much from those of Osteodontornis (as far as can be told in their fragmented state), and may be from an older relative. They are the oldest known remains of large North Pacific pseudotooth birds, but if the enigmatic Cyphornis magnus from the same region dates back to the Paleogene they may well be assignable to that taxon, whatever their systematic affiliations might be beyond that. As few directly comparable bones of sufficient quality exist, the relationship of Osteodontornis to other pseudotooth birds is not completely resolved. As noted above, the entire genus (regardless of how many species can be recognized) may be a junior synonym of Cyphornis. Generally, recent authors have tended to place large Neogene pseudotooth bird fossils from the Atlantic in Pelagornis, and those from the North Pacific in Osteodontornis. It remains to be seen if this east-west division can be upheld, but biogeographically it seems quite sensible at least as a working hypothesis until sufficient well-preserved material has been found to make an in-depth study. It is less clear what to make of the Southern Hemisphere pseudotooth birds fossils, none of which are complete enough for more than the most tentative identification. Many seabirds of our time, such as albatrosses and other Procellariiformes, show a phylogenetic division between Northern and Southern Hemisphere lineages, separated by the Equatorial currents. Whether this also held true in the warmer climate of the Miocene is not known, but the general phylogenetic patterns found in Procellariiformes suggests that the north-south division is rather ancient and evolved even before the Miocene.
From the Neogene of New Zealand "Pseudodontornis" stirtoni has been described, which unlike the rest of its (doubtfully valid) genus is not from the Paleogene Atlantic region. It has been proposed as a monotypic genus Neodontornis, but this has not been widely accepted. It may be valid still, as the bones are of a rather small pseudotooth bird; though apparently too small for Osteodontornis detailed comparisons could be insightful. Its jugal arch is indeed short and very stout behind the orbital process of the prefrontal bone, like in Osteodontornis but apparently unlike in the type species of its supposed genus, P. longirostris. A larger proximal (initially misidentified as distal) humerus piece (CMNZ AV 24,960), probably from the Waiauan (Middle/Late Miocene) and found near the Waipara River mouth, is little if any distinct from O. orri in shape and size; it has a flange at the side and is less straight, but whether these features are natural or due to the damaged state of the specimens is unclear. It also agrees more with Pelagornis than with Paleogene remains from Oregon mentioned above. A distal left humerus end and some wing bone fragments from the Late Oligocene Yamaga Formation of Kitakyūshū (Japan) might be the oldest remains of an Osteodontornis, but their assignment to the present genus is just as uncertain as in the case of the New Zealand fossil. Also from Japan are one or two of the youngest pseudodontorn fossils – a fragmentary right humerus from the Early Pliocene Yushima Formation at Maesawa, and probably also a distal right femur (MFM 1801) from the Early Pleistocene Dainichi Formation at Kakegawa that was initially believed to be from an albatross. These might represent the last survivors of Osteodontornis – the Kakegawa fossil at least is a good match in size –, but require more study before they can be assigned there.