We present kinematics of 135 planetary nebulae in M31 from a survey covering 3.9 square degrees and extending out to 15 kpc from the southwest major axis and more than 20 kpc along the minor axis. The majority of our sample, even well outside the disk, shows significant rotational support (mean line-of-sight velocity 116 km/s). We argue that these PN belong to the outer part of M31's large de Vaucouleurs bulge. Only five PN have velocities clearly inconsistent with this fast rotating bulge. All five may belong to tidal streams in M31's outer halo. One is projected on the Northern Spur, and is counter-rotating with respect to the disk there. Two are projected along the major axis at X=-10 kpc and have M32-like velocities; they could be debris from that galaxy. The remaining two halo PN are located near the center of the galaxy and their velocities follow the gradient found by Ibata et al. (2004), implying that these PN could belong to the Southern Stream. If M31 has a non-rotating, pressure-supported halo, we have yet to find it, and it must be a very minor component of the galaxy.

accepted to ApJ; main body of paper is 36 pages, including 14 figures