We fabricated novel composite (mixed matrix) membranes based on a permeable glassy polymer, Poly(2,6-dimethyl-1,4-phenylene oxide) (PPO), and variable loadings of few-layer graphene, to test their potential in gas separation and CO2 capture applications. The permeability, selectivity and diffusivity of different gases as a function of graphene loading, from 0.3 to 15 wt %, was measured at 35 and 65 °C. Samples with small loadings of graphene show a higher permeability and He/CO2 selectivity than pure PPO, due to a favorable effect of the nanofillers on the polymer morphology. Higher amounts of graphene lower the permeability of the polymer, due to the prevailing effect of increased tortuosity of the gas molecules in the membrane. Graphene also allows dramatically reducing the increase of permeability with temperature, acting as a “stabilizer” for the polymer matrix. Such effect reduces the temperature-induced loss of size-selectivity for He/N2 and CO2/N2, and enhances the temperature-induced increase of selectivity for He/CO2. The study confirms that, as observed in the case of other graphene-based mixed matrix glassy membranes, the optimal concentration of graphene in the polymer is below 1 wt %. Below such threshold, the morphology of the nanoscopic filler added in solution affects positively the glassy chains packing, enhancing permeability and selectivity, and improving the selectivity of the membrane at increasing temperatures. These results suggest that small additions of graphene to polymers can enhance their permselectivity and stabilize their properties.