In this Letter, we announce the discovery of a new dwarf galaxy, Leo T, in the Local Group. It was found as a stellar overdensity in the Sloan Digital Sky Survey Data Release 5 (SDSS DR5). The color-magnitude diagram of Leo T shows two well-defined features, which we interpret as a red giant branch and a sequence of young, massive stars. As judged from fits to the color-magnitude diagram, it lies at a distance of about 420 kpc and has an intermediate-age stellar population with a metallicity of [Fe/H]= -1.6, together with a young population of blue stars of age of 200 Myr. There is a compact cloud of neutral hydrogen with mass roughly 10^5 solar masses and radial velocity 35 km/s coincident with the object visible in the HIPASS channel maps. Leo T is the smallest, lowest luminosity galaxy found to date with recent star-formation. It appears to be a transition object similar to, but much lower luminosity than, the Phoenix dwarf.