A cladistic analysis of the genus Atlantodesmus Hoffman, 2000 is presented. With a total of 11 taxa and 30 morphological characters, and under implied weighting (k = 3), two equally most parsimonious trees (length = 58 steps; total fit = 23.150; CI = 0.64; RI = 0.64) recovered the monophyly of the genus. The resulting synapomorphies are: absence of a ventral projection on the post-gonopodal sternites; presence of folds on the dorsal edge of the prefemoral region of the gonopod; and one homoplastic transformation: presence of a cingulum. In addition, Atlantodesmus sierwaldae sp. nov. is described from the state of Minas Gerais, in the Brazilian Cerrado, and a key to the males of the genus is provided.