The Sloan Digital Sky Survey has revealed an overdensity of luminous red giant stars ∼3° (40 projected kpc) to the northeast of M31, which we have called Andromeda NE. The line-of-sight distance to Andromeda NE is within ∼50 kpc of M31; Andromeda NE is not a physically unrelated projection. Andromeda NE has a g-band absolute magnitude of ∼-11.6 and a central surface brightness of ∼29 mag arcsec-2, making it nearly 2 orders of magnitude more diffuse than any known Local Group dwarf galaxy at that luminosity. Based on its distance and morphology, Andromeda NE is likely undergoing tidal disruption. Andromeda NE's red giant branch color is unlike that of M31's present-day outer disk or the stellar stream reported by Ibata et al., arguing against a direct link between Andromeda NE and these structures. However, Andromeda NE has a red giant branch color similar to that of the G1 clump; it is possible that these structures are both material torn off of M31's disk in the distant past or that these are both part of one ancient stellar stream.