Two chelodesmid millipeds described by Brölemann (1903) from the interior of Bahia have not been reported for over 100 years despite their large size and bright coloration. Originally described as Leptodesmus gounellei and Leptodesmus carminatus, neither species is referable to Leptodesmus as currently defined nor any other established genus. Both have been studied from the type specimens, and are here designated the type species of two new genera, Plectrogonodesmus for gounellei and Baianassa for carminatus. Diagnostic characters are illustrated for both taxa. Intergeneric relationships are at present not evident, and are not suggested pending better understanding of the chelodesmid fauna of eastern Brazil.