Polybenzimidazoles (PBIs) are promising materials for gas separation membranes at elevated temperatures due to their excellent chemical and thermal stability and high Tgs. Their properties make them useful for gas separation of H-2 and CO2 from pre-combustion syngas, which requires operating temperatures of 150-300 degrees C. PBIs have inherently low gas permeabilities, and thus the focus of this work was to improve permeability without sacrificing selectivity or mechanical properties of the membranes. Low molecular weight poly(ethylene oxide) (PEO) or poly(propylene carbonate) (PPC) were incorporated as thermally labile grafts and blends. It was believed that removing these low molecular weight sacrificial components via a controlled heat treatment would allow formation of "nanovoids" in the membrane that could increase the permeabilities. Gas transport for blends of PBI with 7 and 11 wt% of PPC and a PBI-g-PEO copolymer with 13 wt% of PEO were measured before and after heat treatment. Unlike other methods of increasing membrane permeability which results in a selectivity trade-off, heat treatment of these PBI blends and graft copolymers resulted in increases in both H-2 permeability and H-2/CO2 selectivity. The PBI-PPC blend containing 7 wt% of PPC, after heating at 350 degrees C, maintained most of the toughness of the PBI homopolymer.