The gas separation properties of new aromatic poly-1,2,4-triazole and poly-1,3,4-oxadiazole membranes have been systematically investigated. Various functional groups were incorporated as pendent groups onto the polymer backbone of poly-1,2,4-triazoles. A wide permeability/selectivity spectrum was covered with the choice of functional groups incorporated into the polymer backbone of poly-1,3,4-oxadiazoles. High permeabilities were found for poly-1,3,4-oxadiazoles with a 1,1,3-trimethyl-3-phenylindane (PIDA-POD) and a 4,4′(2,2′-diphenyl)hexafluor propane (HF-POD) unit in the polymer backbone, while incorporation of a 4,4′-diphenyl ether unit (DPE-POD) results in a polymer with a low permeability but an extremely high selectivity. While the permeabilities vary over four orders of magnitude, the solubility remains almost constant and, therefore, the increase in permeability is mainly due to an increase in diffusivity. The permeability is discussed in terms of the polymer free volume.