Mrk 1216 is a nearby, early-type galaxy with a small effective radius of 2.8 kpc and a large stellar velocity dispersion of 308 km/s for its K-band luminosity of 1.4x10^11 L_sun. Using integral-field spectroscopy assisted by adaptive optics from Gemini North, we measure spatially resolved stellar kinematics within ~450 pc of the galaxy nucleus. The galaxy exhibits regular rotation with velocities of ± 180 km/s and a sharply peaked velocity dispersion profile that reaches 425 km/s at the center. We fit axisymmetric, orbit-based dynamical models to the combination of these high angular resolution kinematics, large-scale kinematics extending to roughly three effective radii, and Hubble Space Telescope imaging, resulting in a constraint of the mass of the central black hole in Mrk 1216. After exploring several possible sources of systematics that commonly affect stellar-dynamical black hole mass measurements, we find a black hole mass of (4.9±1.7)x10^9 M_sun and a H-band stellar mass-to-light ratio of 1.3±0.4 M_sun/L_sun (1-sigma uncertainties). Mrk 1216 is consistent with the local black hole mass - stellar velocity dispersion relation, but is a factor of ~5-10 larger than expectations from the black hole mass - bulge luminosity and black hole mass - bulge mass correlations when conservatively using the galaxy's total luminosity or stellar mass. This behavior is quite similar to the extensively studied compact galaxy NGC 1277. Resembling the z~2 quiescent galaxies, Mrk 1216 may be a passively evolved descendant, and perhaps reflects a previous era when galaxies contained over-massive black holes relative to their bulge luminosities/masses, and the growth of host galaxies had yet to catch up. ; Comment: accepted for publication in ApJ