We report the discovery of a very cool brown dwarf, ULAS J003402.77-005206.7 (ULAS J0034-00), identified in the UKIRT Infrared Deep Sky Survey First Data Release. 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 J04151954-0935066 (2MASS J0415-09), the latest type and coolest well-studied brown dwarf to date, with effective temperature Teff ~ 750K, 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. Secondly, the H - [4.49] colour provides an empirical estimate of the effective temperature of 540 < Teff < 660K (+/- 2σ range). Thirdly, 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 < Δ Teff < 120K relative to 2MASS J0415-09i.e. 630 < Teff < 690K (+/- 2σ), and lower gravity or higher metallicity according to the degenerate combination -0.5 < Δ(logg - 2[m/H]) < -0.25 (+/- 2σ). Combining these estimates, and considering systematics, it is likely the temperature lies in the range 600 < Teff < 700K. Measurement of the parallax will allow an additional check of the inferred low temperature. Despite the low inferred Teff we find no evidence for strong absorption by NH3 over the wavelength range 1.51-1.56μm. Evolutionary models imply that the mass and age are in the ranges 15-36 MJup and 0.5-8Gyr, respectively. The measured proper motion, of 0.37 +/- 0.07 arcsec yr-1, combined with the photometrically estimated distance of 14-22 pc, implies a tangential velocity of ~30 kms-1, a value consistent with expectation for the inferred age. 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.