Matrimid polyimide gas separation membranes were exposed to different heat treatments between 300 and 525 °C to investigate the intermediate structures that evolve between annealing and carbonization. The exposure time was either 5 or 30 min, while the atmosphere was N2. It was found, using TGA and FTIR, that below 425 °C no thermal decomposition takes place. At higher temperatures thermal decomposition leads to the formation of intermediate structures as the process of carbonization starts. Gas permeation measurements with He, N2, O2, CO2, and C3H6 show that the structure becomes more dense at treatments below the Tg of the polymer, whereas above the Tg a concurrent formation of charge transfer complexes takes place. A steep increase of permeability was found at heat treatments above 475 °C, attributed to the thermal decomposition and the transition to carbon membranes. All heat-treated membranes showed a good resistance to plasticization by C3H6, although the permeability decreased, when compared to untreated membranes. Membranes treated at 475 °C for 30 min showed no plasticization combined with sustained permeation rates.