As part of an ongoing revision and cladistic analysis of the “K92 clade” (Gonyleptidae), the Brazilian genus Progonyleptoidellus Piza, 1940 is revised and two new species from São Paulo State are described: P. bocaina sp. nov. and P. picinguaba sp. nov. A cladistic analysis of the genus was performed using these two new species plus the three previously described species of the genus [P. fuscopictus (B. Soares, 1942); P. orguensis (Soares & Soares, 1954); and P. striatus (Roewer, 1913)], and 25 more additional gonyleptoid outgroup species, most being representatives of the K92 clade. The data matrix is composed of 109 characters: three from the ocularium, 24 from the dorsal scutum, six from the free tergites, nine from the pedipalp, 41 from the legs and 26 from male genitalia. The genus Progonyleptoidellus was recovered as monophyletic only with the exclusion of P. orguensis and was supported on the basis of only one exclusive synapomorphy: presence of dry-marks on sulci of dorsal scutum. Based on the cladistic analysis, P. orguensis was reallocated in Deltaspidium Roewer, 1927, herein considered a senior synonym of Adhynastes Roewer, 1930, and two new combinations are proposed: Deltaspidium orguense (Soares & Soares, 1954) and Deltaspidium tenue (Roewer, 1930). Diagnoses are given for Progonyleptoidellus, the previously described species, (P. fuscopictus and P. striatus) and the two new species.