We present the discovery of an inhomogenous, low-surface brightness, extended disk-like structure around the Andromeda galaxy (M31) based on a large kinematic survey of more than 2800 stars with the Keck/DEIMOS spectrograph. The stellar structure spans radii from 15 kpc out to ~40 kpc, with detections out to R ~ 70 kpc. The constituent stars lag the expected velocity of circular orbits in the plane of the M31 disk by ~40 kms and have a velocity dispersion of ~30 kms. The color range on the upper RGB shows a large spread indicative of a population with a significant range of metallicity. The mean metallicity of the population, measured from Ca II equivalent widths, is [Fe/H] = -0.9 +/- 0.2. The morphology of the structure is irregular at large radii, and shows a wealth of substructures which must be transitory in nature, and are almost certainly tidal debris. The presence of these substructures indicates that the global entity was formed by accretion. This extended disk follows smoothly on from the central parts of M31 disk with an exponential density law of scale-length of 5.1 +/- 0.1 kpc, similar to that of the bright inner disk. The population possesses similar kinematic and abundance properties over the entire region where it is detected in the survey. We estimate that the structure accounts for approximately 10% of the total luminosity of the M31 disk, and given the huge scale, contains ~30% of the total disk angular momentum. This finding indicates that at least some galactic stellar disks are vastly larger than previously thought and are formed, at least in their outer regions, primarily by accretion. [abridged]

20 pages, 30 figures, ApJ submitted