We report on the discovery of high-energy (HE; E > 0.1 GeV) and very high-energy (VHE; E > 100 GeV) gamma-ray emission from the high-frequency-peaked BL Lac object RBS 0413. VERITAS, a ground-based gamma-ray observatory, detected VHE gamma rays from RBS 0413 with a statistical significance of 5.5 standard deviations (sigma) and a gamma-ray flux of (1.5 \pm 0.6stat \pm 0.7syst) \times 10^(-8) photons m^(-2) s^(-1) (\sim 1% of the Crab Nebula flux) above 250 GeV. The observed spectrum can be described by a power law with a photon index of 3.18 \pm 0.68stat \pm 0.30syst. Contemporaneous observations with the Large Area Telescope (LAT) on the Fermi Gamma-ray Space Telescope detected HE gamma rays from RBS 0413 with a statistical significance of more than 9 sigma, a power-law photon index of 1.57 \pm 0.12stat +0.11sys -0.12sys and a gamma-ray flux between 300 MeV and 300 GeV of (1.64 \pm 0.43stat +0.31sys -0.22sys) \times 10^(-5) photons m^(-2) s^(-1). We present the results from Fermi-LAT and VERITAS, including a spectral energy distribution modeling of the gamma-ray, quasi-simultaneous X-ray (Swift-XRT), ultraviolet (Swift-UVOT) and R-band optical (MDM) data. We find that, if conditions close to equipartition are required, both the combined synchrotron self-Compton/external-Compton and the lepto-hadronic models are preferred over a pure synchrotron self-Compton model.