We report the discovery of 30 stars with extreme space velocities ($>$ 480 km/s) in the Gaia-DR2 archive. These stars are a subset of 1743 stars with high-precision parallax, large tangential velocity ($v_{tan}>$ 300 km/s), and measured line-of-sight velocity in DR2. By tracing the orbits of the stars back in time, we find at least one of them is consistent with having been ejected by the supermassive black hole at the Galactic Center. Another star has an orbit that passed near the Large Magellanic Cloud (LMC) about 200 Myr ago. Unlike previously discovered blue hypervelocity stars, our sample is metal-poor (-1.5 $<$ [Fe/H] $<$ -1.0) and quite old ($>$ 1 Gyr). We discuss possible mechanisms for accelerating old stars to such extreme velocities. The high observed space density of this population, relative to potential acceleration mechanisms, implies that these stars are probably bound to the Milky Way (MW). If they are bound, the discovery of this population would require a local escape speed of around $sim$ 600 km/s and consequently imply a virial mass of $M_{200} sim 1.4 times 10^{12} M_odot$ for the MW.