The nearby lenticular galaxy NGC 1277 is thought to host one of the largest black holes known, however the black hole mass measurement is based on low spatial resolution spectroscopy. In this paper, we present Gemini Near-infrared Integral Field Spectrometer observations assisted by adaptive optics. We map out the galaxys stellar kinematics within ~440 pc of the nucleus with an angular resolution that allows us to probe well within the region where the potential from the black hole dominates. We find that the stellar velocity dispersion rises dramatically, reaching ~550 km/s at the center. Through orbit-based, stellar-dynamical models we obtain a black hole mass of (4.9 pm 1.6) x 10^9 Msun (1-sigma uncertainties). Although the black hole mass measurement is smaller by a factor of ~3 compared to previous claims based on large-scale kinematics, NGC 1277 does indeed contain one of the most massive black holes detected to date, and the black hole mass is an order of magnitude larger than expectations from the empirical relation between black hole mass and galaxy luminosity. Given the galaxys similarities to the higher redshift (z~2) massive quiescent galaxies, NGC 1277 could be a relic, passively evolving since that period. A population of local analogs to the higher redshift quiescent galaxies that also contain over-massive black holes may suggest that black hole growth precedes that of the host galaxy.