The coexistence of wax deposition and gas hydrate in deep-water submarine pipelines enhances blockage risk, which is a serious threat to pipeline security. This work applied molecular dynamics (MD) simulations to explore the effect of wax molecules on methane hydrate formation. The growth trajectories, the main structural properties, potential energy, and hydrate cage information of methane hydrate in the absence/presence of wax molecules were analyzed. The simulation results show that the presence of ten C17 n-alkane wax molecules promoted the growth of methane hydrate throughout the simulation, while the presence of one C17 n-alkane wax molecule and one C50 n-alkane wax molecule promoted hydrate growth before 40 ns, subsequently inhibiting it. According to the snapshot information and coordination number of wax molecules, it was concluded that the addition of wax molecule(s) advanced the formation of gas bubbles, while the crystallization of ten C17 n-alkane wax molecules occurred before bubble formation. Additionally, gas–liquid-solid three-phase contact is beneficial to the growth of methane hydrate, while the gas–solid interface distance could be affected by the presence of the wax molecule(s) in the gas bubble. Therefore, the molecular level analysis based on MD simulations showed that the effect of wax molecules on methane hydrate formation was complex, depending on the distribution of the wax molecules and the gas bubble in the system.