Archaeodobenus was the contemporary of the odobenid Pseudotaria from the same formation, which it may have diverged from in the western North Pacific during the Late Miocene.

Archaeodobenus appears to have been closer related to later odobenids such as Imagotaria, Pontolis, the subfamily Odobeninae, whereas Pseudotaria seems to have been more basal.

[1] Unlike the modern walrus, Archaeodobenus did not have tusks but instead had canines of moderate size, and looked more like a sea lion.

[2] The holotype specimen appears to have been a young adult male of about 3 metres (9.8 feet) in length, which would have weighed around 473 kg (1,043 lb).

Archaeodobenus can be distinguished from Pseudotaria by features such as the shape and size of the occipital condyle (which connects with the first neck vertebra at the back of the skull), the foramen magnum (the opening through which the spinal cord passes into the cranium), the mastoid process (where various muscles attach to the back of the skull), and some features in the postcranial skeleton.