Surface nanobubbles have been presumed to lead to the experimental observation that liquid boiling often occurs at a much lower supersaturation than expected, yet no qualitative theory exists to explain how they participate in the process. Here, we report through a simple theoretical analysis on how the metastable nanobubbles nucleate the liquid-to-vapor transition by serving as an intermediate phase. The appearance of metastable nanobubbles inhibits the shrink of the bubble nucleus and changes bubble nucleation into a multistep process. We show three possible mechanisms for heterogeneous nucleation starting from metastable surface nanobubbles: nucleation from pinned nanobubbles, nucleation via nanobubble depinning, and nucleation through nanobubble coalescence, each predicting a significant reduction in a nucleation barrier. The occurrence of a specific nucleation pathway of bubble nucleation depends on the detailed geometry of local substrate roughness. These results give insight into how the appearance of surface nanobubbles changes the nucleation mechanisms of liquid boiling.