The paraphyletic group Grylloblattida, formerly included in the Protorthoptera sensu lato, is of great importance for the phylogeny of some ‘polyneopterous’ orders, because it is currently assumed to contain the sister groups of modern Plecoptera (stoneflies) and Grylloblattodea. We present new discoveries and new observations and interpretations concerning this crucial assemblage. Lodevopterum angustus new genus and species and Depressopterum minutus new species are described from the Upper Permian of the Lodève Basin (Hérault, France). The ‘Grylloblattida’ from Commentry (Allier, France; Upper Carboniferous) are revised: the family Protoblattinidae Meunier, 1909a is restored after the redescription of the type species Protoblattina bouvieri Meunier, 1909a; the family Stenoneuritidae Lameere, 1917 is revised; Palaeocixius fayoli Handlirsch, 1906b and Protoblattina giardi Meunier, 1921 are synonymized with Palaeocixius antiquus Brongniart, 1893, followed by a discussion on the possible familial attributions of this genus. The affinities of the poorly known family Protoperlidae Brongniart, 1885a are discussed after a critical compilation of the available data, i.e., Protoperla boltoni Lameere, 1917 is considered as Grylloblattida incertae sedis and Polyetes elegantissima Meunier, 1921 is transferred into Laurentiaupterum new genus and assigned to Paraphenopteridae new family. Close phylogenetic relationship of Atactophlebia termitoides Martynov, 1928 (Tikhiye Gory, Tatarian Republic, Russia; Upper Permian) and Pinidelia sukatshevae Storozhenko, 1994 (Tyulkino, Perm region, Russia; Upper Permian) is based on a new interpretation of their forewing venation. The recent taxonomy and phylogeny of the Grylloblattida proposed by Storozhenko (1998, 2002) are refuted. The current concepts of Protorthoptera, Plecopteroid Assemblage, and Grylloblattida are compared.