Natural gas (the main component is methane) has been widely used as a fuel and raw material in industry. Removal of nitrogen (N2) from methane (CH4) can reduce the cost of natural gas transport and improve its efficiency. However, their extremely similar size increases the difficulty of separating N2 from CH4. In this study, we have performed a comprehensive investigation of N2 and CH4 adsorption on different charge states of boron nitride (BN) nanocage fullerene, B36N36, by using a density functional theory approach. The calculational results indicate that B36N36 in the negatively charged state has high selectivity in separating N2 from CH4. Moreover, once the extra electron is removed from the BN nanocage, the N2 will be released from the material. This study demonstrates that the B36N36 fullerene can be used as a highly selective and reusable material for the separation of N2 from CH4. The study also provides a clue to experimental design and application of BN nanomaterials for natural gas purification.