All conventional methods to laser-cool atoms rely on repeated cycles of optical pumping and spontaneous emission of a photon by the atom. Spontaneous emission in a random direction provides the dissipative mechanism required to remove entropy from the atom. However, alternative cooling methods have been proposed1,2 for a single atom strongly coupled to a high-finesse cavity; the role of spontaneous emission is replaced by the escape of a photon from the cavity. Application of such cooling schemes would improve the performance of atom-cavity systems for quantum information processing 3,4. Furthermore, as cavity cooling does not rely on spontaneous emission, it can be applied to systems that cannot be laser-cooled by conventional methods; these include molecules2 (which do not have a closed transition) and collective excitations of Bose condensates5, which are destroyed by randomly directed recoil kicks. Here we demonstrate cavity cooling of single rubidium atoms stored in an intracavity dipole trap. The cooling mechanism results in extended storage times and improved localization of atoms. We estimate that the observed cooling rate is at least five times larger than that produced by free-space cooling methods, for comparable excitation of the atom.