One alternative for the storage and transport of hydrogen is blending a low amount of hydrogen (up to 15 or 20%) into existing natural gas grids. When demanded, hydrogen can be then separated, close to the end users using membranes. In this work, composite alumina carbon molecular sieves membranes (Al-CMSM) supported on tubular porous alumina have been prepared and characterized. Single gas permeation studies showed that the H2/CH4 separation properties at 30 °C are well above the Robeson limit of polymeric membranes. H2 permeation studies of the H2–CH4 mixture gases, containing 5–20% of H2 show that the H2 purity depends on the H2 content in the feed and the operating temperature. In the best scenario investigated in this work, for samples containing 10% of H2 with an inlet pressure of 7.5 bar and permeated pressure of 0.01 bar at 30 °C, the H2 purity obtained was 99.4%.