At present, the strongest upper limit on $sum m_{ u}$, the sum of neutrino masses, is from cosmological measurements. However, this bound assumes that the neutrinos are stable on cosmological timescales, and is not valid if the neutrino lifetime is less than the age of the universe. In this paper, we explore the cosmological signals of theories in which the neutrinos decay into invisible dark radiation on timescales of order the age of the universe, and determine the bound on the sum of neutrino masses in this scenario. We focus on the case in which the neutrinos decay after becoming non-relativistic. We derive the Boltzmann equations that govern the cosmological evolution of density perturbations in the case of unstable neutrinos, and solve them numerically to determine the effects on the matter power spectrum and lensing of the cosmic microwave background. We find that the results admit a simple analytic understanding. We then use these results to perform a Monte Carlo analysis based on the current data to determine the limit on the sum of neutrino masses as a function of the neutrino lifetime. We show that in the case of decaying neutrinos, values of $sum m_{ u}$ as large as 0.9 eV are still allowed by the data. Our results have important implications for laboratory experiments that have been designed to detect neutrino masses, such as KATRIN and KamLAND-ZEN.