  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.
