A major challenge to routine non-invasive, nanoscale magnetic imaging is the development of Hall sensors that are stable under ambient conditions and retain low minimum detectable fields down to nanoscale dimensions. To address these issues we have fabricated and characterised chemical vapour deposition (CVD) graphene Hall sensors with wire widths between 50 nm and 1500 nm, in order to exploit the high carrier mobility and tuneability of this material. The measured Hall voltage noise is in good agreement with theoretical models and we demonstrate that minimum detectable fields at fixed drive current are lowest in the vicinity of the charge neutrality point. Our best performing deep sub-micron sensors, based on a wire width of 85 nm, display the excellent room temperature resolution of 59 µT/√Hz at a dc drive current of 12 µA and measurement frequency of 531 Hz. We observe a weak increase in minimum detectable field as the active sensor area is reduced while the Hall offset field is largely independent of size. These figures-of-merit significantly surpass prior results on larger probes in competing materials systems, with considerable scope for further optimisation. Our results clearly demonstrate the feasibility of using CVD graphene to realise very high spatial resolution nanosensors for quantitative room temperature magnetic imaging.