We demonstrate the presence of an extended and massive circumgalactic medium (CGM) around Messier 31 using archival HST Cosmic Origins Spectrograph ultraviolet spectroscopy of 18 QSOs projected within two virial radii of M31 (R sub(vir) = 300 kpc). We detect absorption from Si III at -300 <, ~ v sub(LSR) <, ~ -150 km s super(-1) toward all three sightlines at R <, ~ 0.2R sub(vir), 3 of 4 sightlines at 0.8 <, ~ R/R sub(vir) <, ~ 1.1, and possibly 1 of 11 at 1.1 < R/R sub(vir) <, ~ 1.8. We present several arguments that the gas at these velocities observed in these directions originates from the M31 CGM 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. At R < 0.8R sub(vir), the covering fraction is close to unity for Si III and C IV (functionof sub(c) ~ 60%-97% at the 90% confidence level), but drops to functionof sub(c) <, ~ 10%-20% at R > ~ R sub(vir). We show that the M31 CGM gas is bound, multiphase, predominantly ionized, and is more highly ionized gas at larger R. We estimate using Si II, Si III, and Si IV, a CGM metal mass of > ~2 x 10 super(6) M sub(middot in circle) and gas mass of > ~3 x 10 super(9)(Z sub(middot in circle)/Z) M sub(middot in circle) within 0.2R sub(vir), and possibly a factor of ~10 larger within R sub(vir), implying substantial metal and gas masses in the CGM of M31.