We demonstrate the presence of an extended and massive circumgalactic medium (CGM) around Messier 31 using archival HST COS ultraviolet spectroscopy of 18 QSOs projected within two virial radii of M31 (Rvir=300 kpc). We detect absorption from SiIII at -300<vLSR}<-150 km/s toward all 3 sightlines at R<0.2Rvir, 3 of 4 sightlines at 0.8<R/Rvir<1.1, and possibly 1 of 11 at 1.1<R/Rvir<1.8. We present several arguments that the gas at these velocities observed in these directions originates from the CGM of M31 rather than the Local Group or Milky Way CGM or Magellanic Stream. We show that the dwarf galaxies located in the CGM of M31 have very similar velocities over similar projected distances from M31. We find a non-trivial relationship only at these velocities between the column densities (N) of all the ions and R, whereby N decreases with increasing R. Singly ionized species are only detected in the inner CGM of M31 at R<0.2Rvir. At R<0.8 Rvir, the covering fraction is close to unity for SiIII and CIV (fc~60%-97% at the 90% confidence level), but drops to fc<10-20% at R>Rvir. We show that the M31 CGM gas is bound, multiphase, predominantly ionized (i.e., HII>>HI), and becomes more highly ionized gas at larger R. We estimate using SiII, SiIII, and SiIV a CGM metal mass of at least 2x10^6 Msun and gas mass of >3x10^9(Zsun/Z) Msun within 0.2 Rvir, and possibly a factor ~10 larger within Rvir, implying substantial metal and gas masses in the CGM of M31. Compared with galaxies in the COS-Halos survey, the CGM of M31 appears to be quite typical for a L* galaxy.