Nematic order resulting from the partial melting of density-waves has been proposed as the mechanism to explain nematicity in iron-based superconductors. An outstanding question, however, is whether the microscopic electronic model for these systems -- the multi-orbital Hubbard model -- displays such an ordered state as its leading instability. In contrast to usual electronic instabilities, such as magnetic and charge order, this fluctuation-driven phenomenon cannot be captured by the standard RPA method. Here, by including fluctuations beyond RPA in the multi-orbital Hubbard model, we derive its nematic susceptibility and contrast it with its ferro-orbital order susceptibility, showing that its leading instability is the spin-driven nematic phase. Our results also demonstrate the primary role played by the $d_{xy}$ orbital in driving the nematic transition, and reveal that high-energy magnetic fluctuations are essential to stabilize nematic order in the absence of magnetic order.