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 bouvieriMeunier, 1909a; the family Stenoneuritidae Lameere, 1917 is revised; Palaeocixius fayoliHandlirsch, 1906b and Protoblattina giardiMeunier, 1921 are synonymized with Palaeocixius antiquusBrongniart, 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 boltoniLameere, 1917 is considered as Grylloblattida incertae sedis and Polyetes elegantissimaMeunier, 1921 is transferred into Laurentiaupterum new genus and assigned to Paraphenopteridae new family. Close phylogenetic relationship of Atactophlebia termitoidesMartynov, 1928 (Tikhiye Gory, Tatarian Republic, Russia; Upper Permian) and Pinidelia sukatshevaeStorozhenko, 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.