Two new species belonging to the genus Anastrepha, A. maya sp. nov. and A. relicta sp. nov., are described. These species are noteworthy because they are closely related to A. tripunctata van der Wulp, an endemic Mexican species currently classified in the cryptostrepha species group, which may be the basal lineage of the genus. These new species come from several tropical Mexican localities and share several taxonomic characters found only in A. tripunctata. The eight known species of the cryptostrepha group are keyed, and a discussion of the phylogenetic relationships between this group and other species groups of Anastrepha is presented.