(abridged) We report the discovery of a very cool brown dwarf, ULAS J003402.77-005206.7 (ULAS J0034-00), identified in UKIDSS DR1. We provide optical, near-infrared, and mid-infrared photometry of the source, and two near-infrared spectra. Comparing the spectral energy distribution of ULAS J0034-00 to that of the T8 brown dwarf 2MASS J0415-09, the latest-type and coolest well-studied brown dwarf to date, with Teff~750 K, we find evidence that ULAS J0034-00 is significantly cooler. First, the measured values of the near-infrared absorption spectral indices imply a later classification, of T8.5. Second, the H-[4.49] colour provides an empirical estimate of the temperature of 540<Teff<660 K (+/-2sig range). Third, the J- and H-band peaks are somewhat narrower in ULAS J0034-00, and detailed comparison against spectral models calibrated to 2MASS J0415-09 yields an estimated temperature lower by 60-120 K relative to 2MASS J0415-09 i.e. 630<Teff<690 K (+/-2sig), and lower gravity or higher metallicity according to the degenerate combination -0.5<delta(log g-2[m/H])<-0.25 (+/-2sig). Combining these estimates, and considering systematics, it is likely the temperature lies in the range 600<Teff<700 K. Despite the low inferred Teff we find no evidence for strong absorption by NH3 over the wavelength range 1.51-1.56 um. Evolutionary models imply that the mass and age are in the ranges 15-36 M(Jup) and 0.5-8 Gyr, respectively. The measured proper motion, of (0.37+/-0.07)arcsec/yr, combined with the photometrically estimated distance of 14-22 pc, implies a tangential velocity of ~30 km/s. ULAS J0034-00 is significantly bluer than 2MASS J0415-09 in Y-J, so future searches should allow for the possibility that cooler T dwarfs are bluer still.