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 × 108M⊙ and an effective radius (Re) of 25 pc. With an effective surface mass density of 9.4 × 1010M⊙ 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 Mg = -14.2 mag, and a spectral energy distribution consistent with an old (14 Gyr) stellar population with [Fe/H] = 0.0 and [α/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.