We report on the properties of the most massive ultra-compact dwarf galaxy (UCD) in the nearby Virgo Cluster of galaxies using imaging from the Next Generation Virgo Cluster Survey and spectroscopy from Keck/DEIMOS. This object (M59-UCD3) appears to be associated with the massive Virgo galaxy M59 (NGC 4621), has an integrated velocity dispersion of 78 km s(-1), a dynamical mass of 3.7 x 10(8)M(circle dot), and an effective radius (R-e) of 25 pc. With an effective surface mass density of 9.4 x 10(10)M(circle dot) kpc(-2), it is the densest galaxy in the local universe discovered to date, surpassing the density of the luminous Virgo UCD, M60-UCD1. M59-UCD3 has a total luminosity of M-g' = -14.2 mag, and a spectral energy distribution consistent with an old (14 Gyr) stellar population with [Fe/H] = 0.0 and [alpha/Fe] = +0.2. We also examine deep imaging around M59 and find a broad low surface brightness stream pointing toward M59-UCD3, which may represent a tidal remnant of the UCD progenitor. This UCD, along with similar objects like M60-UCD1 and M59cO, likely represents an extreme population of tidally stripped galaxies more akin to larger and more massive compact early-type galaxies than to nuclear star clusters in present-day dwarf galaxies.