The type-series of Paraprogynotaenia jimenezi Rysavy, 1966 [type-species of Paraprogynotaenia Rysavy, 1966] from Charadrius wilsonia Ord in Cuba and P. charadrii (Yamaguti, 1956) (= Proterogynotaenia charadrii Yamaguti, 1956) from C. alexandrinus L. in Japan are redescribed. Two new species are described: Paraprogynotaenia minuta n. sp. from C. alexandrinus on the Black Sea coast of Bulgaria [type-host and type-locality, based on specimens previously reported as P. charadrii], from the same host species in Tunisia and from "Tringa totanus" (the host identification is uncertain) in France [the latter two samples were previously reported as Progynotaenia odhneri Nybelin, 1916]; and Paraprogynotaenia canarisi n. sp. from C. marginatus Vieillot in the Republic of South Africa [type-host and type-locality] and from C. alexandrinus and Pluvialis dominica (Müller) in Taiwan [specimens from both localities were previously reported as Paraprogynotaenia charadrii]. P. jimenezi can be distinguished from its congeners by having 12 hooks of equal length. Among the remaining species with 18-22 hooks of varying length, P. minuta n. sp. can be distinguished by the smaller number of proglottides: up to 8 vs 15-20 for P. charadrii and P. canarisi n. sp. The latter two species can be differentiated from one another by the blade length/total length ratio of the smallest (lateral) rostellar hooks, which is less than 0.5 for P. canarisi n. sp. and 0.5 or more for P. charadrii. An identification key to the species of Paraprogynotaenia is provided and the generic diagnosis is amended. A phylogenetic analysis based on 17 morphological characters resulted in the following hypothesis for the relationships within the genus: (P. jimenezi (P. minuta (P. charadrii, P. canarisi))).