Flight poses unique challenges along the body size spectrum. Cockroaches (Blattodea) are a useful system for the study of insect wings because they have a huge body size spectrum, are hindwing-only fliers, and are hypothesized to have had multiple large modifications to their flight morphology over their deep evolutionary history. A preliminary systematic investigation of little-known cockroach taxa (e.g., Oulopterygidae, Anaplectidae) revealed a more complex evolutionary history of wings than previously thought. Thus, we infer the evolutionary history of Blattodea using 41 genes and 91 species in a maximum likelihood framework. We test support for various topologies to account for phylogenetic uncertainty while inferring the evolutionary history of wing morphology and body size with a focus on apical expansions of the hind wing. We find that the ancestral cockroach had wings but without an apical expansion. Hindwings gained an apical expansion nine times independently and the size increase of the expansion negatively correlates with body length. This contradicts the expectation that increased wing-loading at larger spatial scales will favor expansion of the wing. To reconcile this, we suggest that maximum size of flying species is limited by wing structural integrity and minimum body size is limited by the capacity to adopt non-membranous wing morphology.