  We present evidence for a metal-poor, [Fe/H]$\sim-1.4$ $\sigma$=0.2 dex,
stellar halo component detectable at radii from 10 kpc to 70 kpc, in our
nearest giant spiral neighbor, the Andromeda galaxy. This metal-poor sample
underlies the recently-discovered extended rotating component, and has no
detected metallicity gradient. This discovery uses a large sample of 9861
radial velocities of Red Giant Branch (RGB) stars obtained with the Keck-II
telescope and DEIMOS spectrograph, with 827 stars with robust radial velocity
measurements isolated kinematically to lie in the halo component primarily by
windowing out the extended rotating component which dominates the photometric
profile of Andromeda out to $<$50 kpc (de-projected). The stars lie in 54
spectroscopic fields spread over an 8 square degree region, and are expected to
fairly sample the halo to a radius of $\sim$70 kpc. The halo sample shows no
significant evidence for rotation. Fitting a simple model in which the velocity
dispersion of the component decreases with radius, we find a central velocity
dispersion of $152\kms$ decreasing by $-0.90\kms/\kpc$. By fitting a
cosmologically-motivated NFW halo model to the halo stars we constrain the
virial mass of M31 to be greater than $9.0 \times 10^{11} \msun$ with 99%
confidence. The properties of this halo component are very similar to that
found in our Milky Way, revealing that these roughly equal mass galaxies may
have led similar accretion and evolutionary paths in the early Universe.
