We present first results from a spectroscopic survey designed to examine the metallicity and kinematics of individual red giant branch stars in the outer halo of the Andromeda spiral galaxy ( M31 ) . This study is based on multislit spectroscopy with the Keck II 10-m telescope and Low Resolution Imaging Spectrograph of the Ca ii near-infrared triplet in 99 M31 halo candidates in a field at R = 19 kpc on the SE minor axis with brightnesses from 20 < I < 22 . The spectra are used to isolate M31 halo red giants from foreground Milky Way dwarf stars , faint compact background galaxies , and M31 disk giants . The observed distribution of radial velocities is well fit by an equal mix of foreground Milky Way dwarf stars , drawn from a standard Galactic model and with velocities v \lesssim 0 km s ^ { -1 } , and M31 halo giants represented by a Gaussian of width \sigma _ { v } ^ { M 31 } \sim 150 km s ^ { -1 } centered on its systemic velocity of v _ { sys } ^ { M 31 } \approx - 300 km s ^ { -1 } . A secure sample of 29 M31 red giant stars is identified on the basis of radial velocity ( v < -220 km s ^ { -1 } ) , and , in the case of four intermediate-velocity stars ( -160 < v < -220 km s ^ { -1 } ) , broadband B - I color . For this sample of objects , there is rough agreement between the metallicities derived in independent ways : two different calibrations of the Ca ii absorption line strength and a photometric estimate based on fitting model stellar isochrones to an object ’ s location in a ( B - I,~ { } I ) color-magnitude diagram . The [ Fe/H ] distribution of M31 halo giants has an rms spread of at least 0.6 dex and spans the \gtrsim 2 dex range over which the abundance measurement methods are calibrated . The mean/median metallicity of the M31 halo is about \langle [ Fe / H ] \rangle = -1.9 to -1.1 dex ( depending on the details of metallicity calibration and sample selection ) and possibly higher : the high-metallicity end of the distribution is poorly constrained by our data since the selection function for the secure M31 sample excludes > 80 \% of the giants in solar/super-solar metallicity range . Possible reasons are explored for the apparent discrepancy between the mean [ Fe/H ] found in our spectroscopic survey ( corrected for metallicity selection bias ) and the slightly higher mean values found in earlier photometric studies . Field halo red giants in M31 appear to be somewhat more metal-rich on average than their Milky Way counterparts . The M31 halo [ Fe/H ] distribution is comparable to that of M31 globular clusters , Galactic globular clusters , and Local Group dwarf satellite galaxies . The data in this 19 kpc outer halo field are broadly consistent with a scenario in which the halo is built from the accretion of small stellar subsystems . There are four stars in the secure M31 sample which have particularly strong Ca ii lines indicating solar metallicity , at a common velocity of \approx - 340 km s ^ { -1 } close to the galaxy ’ s systemic velocity , similar to what might be expected for M31 disk giants on the minor axis . An extrapolation of the inner disk brightness profile , however , falls far short of accounting for these four stars—the disk would instead have to be very large ( R _ { disk } \gtrsim 80 kpc ) and/or warped . More likely , these four stars represent a metal-rich debris trail from a past accretion event in the halo .