When transitioning to a 100% renewable energy system storing electricity becomes a focal point, as the resource flexibility is lost and the design of the energy system needs to provide flexibility and balancing options to integrate intermittent renewable resources. Using technologies such as power-to-gas offers an opportunity to store electricity in chemical form, which can be used as a long-term storage option. This paper develops a spatial modelling method by using a GIS tool to investigate potential generation sites for power-to-gas plants. The method determines the location of the plants by carbon source potential, proximity of the grid, costs of grid transmission and investment costs of the technology itself. By combining these types of data, it is possible to identify the investment costs of the power-to-gas plants. The method focuses on two paths: biogas upgrade and CO2 methanation. The method is applied to a specific case by investigating the power-to-gas potential in Denmark. The potential and spatial deployment is found by examining the investment costs of plants with an annual gas production of 60 GWh. The findings of the analysis indicate that the biogas upgrade path is the cheapest one of the two, at the present cost level, but due to the relatively small number of biogas plants in Denmark, the chosen plant size is limited to around 55 plants. CO2 methanation is a more costly path, but it has a larger potential of around 800 plants. As the analysis is based on the current sources for biogas and CO2, it is important to emphasise that the potential for CO2 methanation plants can be expected to diminish in the future as more renewable energy is introduced, lowering the need for thermal energy producers, while biogas production could see an increase. Nevertheless, the analysis of a specific case shows that the method gives a good indication of the extent of the power-to-gas resources by using a novel approach to the matter. The method can be applied in other countries as well, giving it a wide appeal.