The halos of galaxies preserve unique records of their formation histories. We carry out the first combined observational and theoretical study of phase-space halo substructure in an early-type galaxy: M87, the central galaxy in the Virgo cluster. We analyze an unprecedented wide-field, high-precision photometric and spectroscopic data set for 488 globular clusters (GCs), which includes new, large-radius Subaru/Suprime-Cam and Keck/DEIMOS observations. We find signatures of two substructures in position-velocity phase space. One is a small, cold stream associated with a known stellar filament in the outer halo; the other is a large shell-like pattern in the inner halo that implies a massive, hitherto unrecognized accretion event. We perform extensive statistical tests and independent metallicity analyses to verify the presence and characterize the properties of these features, and to provide more general methodologies for future extragalactic studies of phase-space substructure. The cold outer stream is consistent with a dwarf galaxy accretion event, while for the inner shell there is tension between a low progenitor mass implied by the cold velocity dispersion, and a high mass from the large number of GCs, which might be resolved by a 0.5 L* E/S0 progenitor. We also carry out proof-of-principle numerical simulations of the accretion of smaller galaxies in an M87-like gravitational potential. These produce analogous features to the observed substructures, which should have observable lifetimes of 1Gyr. The shell and stream GCs together support a scenario where the extended stellar envelope of M87 has been built up by a steady rain of material that continues until the present day. This phase-space method demonstrates unique potential for detailed tests of galaxy formation beyond the Local Group.