Power-to-gas is an energy storage and vector technology which can utilize off-peak power, assist in the integration of renewable power and provide needed fuel for industry and transportation. Further, power-to-gas is a useful technology for balancing surplus baseload and renewable energy generation with demand. There are numerous applications of power-to-gas in Europe, where renewable power is used to generate hydrogen for numerous applications. Examining each of these power-to-gas pathways across quantitative and qualitative criteria, this paper utilizes the stochastic fuzzy analytic hierarchy process to determine criteria weights. These weights are then fed to a multiple criteria decision analysis tool to determine the viability of each pathway for investors and policy makers. A sensitivity analysis is carried out by reprioritizing the criteria and re-evaluating the multiple criteria analysis. The two pathways that score highest under multiple criteria rankings are power-to-gas to mobility-fuel and power-to-gas-to-power, due to their established technologies, lower costs and environmental performance. By extension, both of these power-to-gas pathways are the most appropriate ways for this technology to be implemented, due to their combination of public familiarity, emissions reductions, and developed, available technologies.