I report the quantum Cramér-Rao bound on the sensitivity of mass-sensing with a nano-mechanical resonator as function of its quantum state. I then identify the quantum states which allow the largest sensitivity for a given maximum energy. I show that even with a classical state of existing carbon nanotube resonators it should be possible in principle to measure one thousandth of the mass of an electron. Further improvements might enable reaching a regime where one can measure the relativistic change of mass due to absorption of a single photon, or the creation of a chemical bond.