We report the discovery of a new dwarf galaxy, Andromeda XXIX (And XXIX), using data from the recently released Sloan Digital Sky Survey Data Release 8, and confirmed by Gemini North telescope Multi-Object Spectrograph imaging data. And XXIX appears to be a dwarf spheroidal galaxy, separated on the sky by a little more than 15° from M31, with a distance inferred from the tip of the red giant branch of 730±75 kpc, corresponding to a three-dimensional separation from M31 of 207+20_- 2_ kpc (close to M31's virial radius). Its absolute magnitude, as determined by comparison to the red giant branch luminosity function of the Draco dwarf spheroidal, is MV= -8.3±0.4. And XXIX's stellar populations appear very similar to Draco's; consequently, we estimate a metallicity for And XXIX of [Fe/H] ~-1.8. The half-light radius of And XXIX is 360±60 pc and its ellipticity is 0.35±0.06, typical of dwarf satellites of the Milky Way and M31 at this absolute magnitude range.