Mass accuracy is a key parameter of mass spectrometric performance. TOF instruments can reach low parts per million, and FT-ICR instruments are capable of even greater accuracy provided ion numbers are well controlled. Here we demonstrate sub-ppm mass accuracy on a linear ion trap coupled via a radio frequency-only storage trap (C-trap) to the orbitrap mass spectrometer (LTQ Orbitrap). Prior to acquisition of a spectrum, a background ion originating from ambient air is first transferred to the C-trap. Ions forming the MS or MS(n) spectrum are then added to this species, and all ions are injected into the orbitrap for analysis. Real time recalibration on the "lock mass" by corrections of mass shift removes mass error associated with calibration of the mass scale. The remaining mass error is mainly due to imperfect peaks caused by weak signals and is addressed by averaging the mass measurement over the LC peak, weighted by signal intensity. For peptide database searches in proteomics, we introduce a variable mass tolerance and achieve average absolute mass deviations of 0.48 ppm (standard deviation 0.38 ppm) and maximal deviations of less than 2 ppm. For tandem mass spectra we demonstrate similarly high mass accuracy and discuss its impact on database searching. High and routine mass accuracy in a compact instrument will dramatically improve certainty of peptide and small molecule identification.