Sensors play an important part in many aspects of daily life such as infrared sensors in home security systems, particle sensors for environmental monitoring and motion sensors in mobile phones. High-quality optical microcavities are prime candidates for sensing applications because of their ability to enhance light-matter interactions in a very confined volume. Examples of such devices include mechanical transducers, magnetometers, single-particle absorption spectrometers, and microcavity sensors for sizing single particles and detecting nanometre-scale objects such as single nanoparticles and atomic ions. Traditionally, a very small perturbation near an optical microcavity introduces either a change in the linewidth or a frequency shift or splitting of a resonance that is proportional to the strength of the perturbation. Here we demonstrate an alternative sensing scheme, by which the sensitivity of microcavities can be enhanced when operated at non-Hermitian spectral degeneracies known as exceptional points. In our experiments, we use two nanoscale scatterers to tune a whispering-gallery-mode micro-toroid cavity, in which light propagates along a concave surface by continuous total internal reflection, in a precise and controlled manner to exceptional points. A target nanoscale object that subsequently enters the evanescent field of the cavity perturbs the system from its exceptional point, leading to frequency splitting. Owing to the complex-square-root topology near an exceptional point, this frequency splitting scales as the square root of the perturbation strength and is therefore larger (for sufficiently small perturbations) than the splitting observed in traditional non-exceptional-point sensing schemes. Our demonstration of exceptional-point-enhanced sensitivity paves the way for sensors with unprecedented sensitivity.