We show how the generation of right-handed neutrino masses in Majoron models may be associated with a first-order phase transition and accompanied by the production of a stochastic background of gravitational waves (GWs). We explore different energy scales with only renormalizable operators in the effective potential. If the phase transition occurs above the electroweak scale, the signal can be tested by future interferometers. We consider two possible energy scales for phase transitions below the electroweak scale. If the phase transition occurs at a GeV, the signal can be tested at LISA and provide a complementary cosmological probe to right-handed neutrino searches at the FASER detector. If the phase transition occurs below 100 keV, we find that the peak of the GW spectrum is two or more orders of magnitude below the putative NANOGrav GW signal at low frequencies, but well within reach of the SKA and THEIA experiments. We show how searches of very low frequency GWs are motivated by solutions to the Hubble tension in which ordinary neutrinos interact with the dark sector. We also present general calculations of the phase transition and Euclidean action that apply beyond Majoron models.