Leptogenesis is arguably the best motivated theory of baryogenesis given the discovery of finite neutrino masses, yet its experimental test is elusive given its high energy scale. We discuss gravitational waves (GWs) produced via graviton bremsstrahlung in right-handed neutrino decays during leptogenesis. The presence of right-handed neutrinos in the early universe can lead to a period of early matter domination. In this context, the resultant GW spectrum scales quadratically with the right-handed neutrino mass, while its peak frequency scales inversely with the Yukawa coupling. Detecting such a spectrum would provide strong evidence for leptogenesis and the existence of heavy right-handed neutrinos. We also discuss how the GW spectrum emitted from the thermal plasma is altered by an era of early matter domination. We show that it can mimic the effects of additional relativistic degrees of freedom and a higher reheating temperature, and that information from the graviton bremsstrahlung GW spectrum can break this degeneracy.