The high-frequency-peaked BL Lacertae object RGB J0710+591 was observed in the very high-energy (VHE; E > 100 GeV) wave band by the VERITAS array of atmospheric Cherenkov telescopes. The observations, taken between 2008 December and 2009 March and totaling 22.1 hr, yield the discovery of VHE gamma rays from the source. RGB J0710+591 is detected at a statistical significance of 5.5 standard deviations (5.5σ) above the background, corresponding to an integral flux of (3.9 ± 0.8) × 10 –12 cm –2 s –1 (3% of the Crab Nebula's flux) above 300 GeV. The observed spectrum can be fit by a power law from 0.31 to 4.6 TeV with a photon spectral index of 2.69 ± 0.26 stat ± 0.20 sys . These data are complemented by contemporaneous multiwavelength data from the Fermi Large Area Telescope, the Swift X-ray Telescope, the Swift Ultra-Violet and Optical Telescope, and the Michigan-Dartmouth-MIT observatory. Modeling the broadband spectral energy distribution (SED) with an equilibrium synchrotron self-Compton model yields a good statistical fit to the data. The addition of an external-Compton component to the model does not improve the fit nor brings the system closer to equipartition. The combined Fermi and VERITAS data constrain the properties of the high-energy emission component of the source over 4 orders of magnitude and give measurements of the rising and falling sections of the SED.