El género fue descubierto en un farallón cercano al Lago Colhué Huapi en la localidad La Cantera, en la provincia de Chubut, en Argentina, en sedimentos correspondientes a la formación Sarmiento, que data de finales del Oligoceno (edad mamífero Deseadense).
[1] El nombre del género Maddenia es en homenaje al paleontólogo Richard Madden, por sus aportes a la paleontología de América del Sur, en tanto que el nombre de la especie tipo y única conocida, Maddenia lapidaria, deriva del latín lapidarius, "de piedra".
[1] Esta especie se basa en el holotipo MPEF PV 7735, un fragmento de maxilar con dientes molares y premolares asociados y un canino parcial asociado, además de varios ejemplares adicionales que incluyen varios dientes aislados y otros fragmentos de mandíbulas.
Sus molares eran altos, con coronas complejas y caninos moderadamente desarrollados, características propias de los astrapoterios avanzados de gran tamaño del Oligoceno y el Mioceno (como Astrapotherium y Granastrapotherium), lo que sugiere que debió de ocupar un hábitat diferenciado con respecto a otras formas de gran tamaño, y que por sus características anatómicas constituye una forma intermedia entre los astrapoterios primitivos como Albertogaudrya y astrapotéridos como Parastrapotherium, con los que conforman taxones hermanos a las dos subfamilias de la familia Astrapotheriidae, Astrapotheriinae y Uruguaytheriinae.
[1] Cladograma según Bond et al., 2011, destacando la posición filogenética de Maddenia:[2] Eoastrapostylops Trigonostylops Tetragonostylops Antarctodon Albertogaudrya Scaglia Astraponotus Maddenia Parastrapotherium Astrapotherium Granastrapotherium