I will discuss first results from a Keck/DEIMOS survey to measure radial velocities for several thousand red giant branch stars in the diffuse outskirts of M31. Results to date concern kinematics of stars in the giant stellar stream and in other areas where our team has discovered faint stellar substructure. Combining these radial velocities with inferences from deep HST/ACS colour magnitude diagrams, we can begin to place constraints on the origin of the the structure in the M31 halo.