Uiterlijk leken de Protemnodon-soorten op wallaby's, maar ze waren groter en robuuster. De Nieuw-Guinese soorten waren met een gewicht van 40 tot 50 kg de kleinste soorten en vergelijkbaar met het formaat van de hedendaagse oostelijke grijze reuzenkangoeroe (Macropus giganteus). De Australische soorten wogen tot meer dan 110 kg, waarbij deze schattingen van het lichaamsgewicht gebaseerd zijn op de omtrek van het dijbeen. P. anak uit Tasmanië was met een hoogte van twee meter de grootste soort. De Nieuw-Guinese P. tumbuna was zeer uitzonderlijk voor een kangoeroe. Op basis van een vrijwel compleet skelet blijkt uit de bouw van de schouders, de krachtige voorpoten en de korte achterpoten dat deze soort zich op vier poten voortbewoog als een buideldas in plaats van te springen als een kangoeroe.
Fossiele vondsten
Fossielen van Protemnodon-soorten zijn van verschillende locaties in Australië bekend. In Nieuw-Guinea zijn vondsten gedaan in onder meer de Otibanda-formatie uit het Plioceen en Nombe Rockshelter uit het Laat-Pleistoceen.