Methane is the second largest contributor to global warming after CO2, and it is hard to abate due to its low concentration in the emission sources and in the atmosphere. However, removing methane from the atmosphere will accelerate achieving net-zero targets, since its global warming potential is 28 over a 100-year period. This work presents first-of-its-kind process concepts for co-removal of methane and CO2 that combines the catalytic conversion of methane step (thermal/photo-catalytic) with CO2 capture. Proposed processes have been analyzed for streams with lean methane concentrations, which are non-fossil emissions originating in the agricultural sector or natural emissions from wetlands. If the proposed processes can overcome challenges in catalyst/material design to convert methane at low concentrations, they have the potential to remove more than 40% of anthropogenic and natural methane emissions from the atmosphere at a lower energy penalty than the state-of-the-art technologies for direct air capture of CO2.