The search for cleaner and more sustainable energy sources is increasingly growing. Aligning this demand with another environmental problem, such as sewage treatment/disposal, is a strategic priority. In light of this, the aim of this study was to estimate the energy potential of sewage generated in the Brazilian state of São Paulo (SP) by using it to produce biomethane. The study also evaluated the viability of using this byproduct of sewage treatment (biomethane) as a substitute for natural gas (NG), as both of them have similar lower heat values. To do this, information was gathered regarding the population, gross domestic product per capita, sewage collected, and natural gas consumption for each of the state’s 645 cities, and, based on this, the sewage energy potential, the amount of NG to be substituted by biomethane, and the reduction in CO₂ emissions were calculated. Moreover, in order to address a possible allocation of biomethane that could potentially be produced in each SP city and sent to currently NG-consuming cities, an optimization algorithm was proposed. The results indicated a sewage energy potential of 4.68 × 10⁹ kWh/yr for the entire SP state, which would be enough to supply around 10% of the energy value of all the NG currently consumed. It was also observed that from 130 cities with NG consumption, 10 could produce enough biomethane to fully satisfy the natural gas demand. In the elected scenario of optimization, 291 cities were found to be capable of supplying the demand of 26 cities that currently use NG. The potential to reduce CO₂ emissions is between 1.81 × 10⁶ and 2.42 × 10⁶ ton/yr, and this range could increase if sewage treatment coverage grows. Despite the challenges inherent in extrapolating a potential study to scenarios that require significative investment, the results obtained are useful for formulating public policies for decarbonization in the near future.