We present the discovery of a brown dwarf companion to the debris disk host star HR 2562. This object, discovered with the Gemini Planet Imager (GPI), has a projected separation of 20.3 +/- 0.3 au (0".618 +/- 0".004) from the star. With the high astrometric precision afforded by GPI, we have confirmed, to more than 5 sigma, the common proper motion of HR 2562B with the star, with only a month-long time baseline between observations. Spectral data in the J-, H-, and K-bands show a morphological similarity to L/T transition objects. We assign a spectral type of L7 +/- 3 to HR 2562B. and derive a luminosity of log(L-bol/L-circle dot) = -4.62 +/- 0.12, corresponding to a mass of 30 +/- 15 M-Jup from evolutionary models at an estimated age of the system of 300-900 Myr. Although the uncertainty in the age of the host star is significant, the spectra and photometry exhibit several indications of youth for HR 2562B. The source has a position angle that is consistent with an orbit in the same plane as the debris disk recently resolved with Herschel. Additionally, it appears to be interior to the debris disk. Though the extent of the inner hole is currently too uncertain to place limits on the mass of HR 2562B, future observations of the disk with higher spatial resolution may be able to provide mass constraints. This is the first brown-dwarf-mass object found to reside in the inner hole of a debris disk, offering the opportunity to search for evidence of formation above the deuterium burning limit in a circumstellar disk.