Mechanical resonators are widely used as inertial balances to detect small quantities of adsorbed mass through shifts in oscillation frequency(1). Advances in lithography and materials synthesis have enabled the fabrication of nanoscale mechanical resonators(2-6), which have been operated as precision force(7), position(8,9) and mass sensors(10-15). Here we demonstrate a room-temperature, carbon-nanotube-based nanomechanical resonator with atomic mass resolution. This device is essentially a mass spectrometer with a mass sensitivity of 1.3 x 10(-25) kg Hz(-1/ 2) or, equivalently, 0.40 gold atoms Hz(-1/2). Using this extreme mass sensitivity, we observe atomic mass shot noise, which is analogous to the electronic shot noise(16,17) measured in many semiconductor experiments. Unlike traditional mass spectrometers, nanomechanical mass spectrometers do not require the potentially destructive ionization of the test sample, are more sensitive to large molecules, and could eventually be incorporated on a chip.