The Sloan Digital Sky Survey has revealed an overdensity of luminous red giant stars ~ 3 degrees (40 projected kpc) to the northeast of M31, which we have called Andromeda NE. The line-of-sight distance to Andromeda NE is within approximately 50 kpc of M31; Andromeda NE is not a physically unrelated projection. Andromeda NE has a g-band absolute magnitude of ~ -11.6 and central surface brightness of ~ 29 mag/sq.arcsec, making it nearly two 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 NEs red giant branch color is unlike that of M31s present-day outer disk or the stellar stream reported by Ibata et al. (2001), 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 M31s disk in the distant past, or that these are both part of one ancient stellar stream.