Thermally rearranged polybenzoxazoles (TR-PBO) are some of the most promising materials for gas separation because of their microporous and bimodal cavities that offer high gas transport performance. However, the brittleness of fully converted TR-PBO membranes has impeded their widespread industrial implementation. In this study, we prepared novel, thermally rearranged poly(benzoxazole-co-imide) membranes (TR-PBOI) with improved mechanical strength and good gas separation performance. These membranes are based on two commercially available TR-able diamines and two non-TR-able diamines with various compositions and different polymer rigidities. TR-PBOI membranes with the appropriate ratio of PBO and PI displayed a high fractional free volume and therefore exceptional gas separation properties (CO2 permeability over 300 barrer and CO2/N2 ideal selectivity above 20); both these values were higher than those of the corresponding original TR-PBO membranes. Furthermore, a substantial improvement in the mechanical properties of TR-PBOI membranes relative to their TR-PBO counterparts was observed.