Here, we report on the discovery of high-energy (HE; E > 0.1 GeV) and very high energy (VHE; E > 100 GeV) γ-ray emission from the high-frequency-peaked BL Lac object RBS 0413. VERITAS, a ground-based γ-ray observatory, detected VHE γ rays from RBS 0413 with a statistical significance of 5.5 standard deviations (σ) and a γ-ray flux of (1.5 ± 0.6stat ± 0.7syst) × 10–8 photons m–2 s–1 (~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 ± 0.68stat ± 0.30syst. Contemporaneous observations with the Large Area Telescope (LAT) on the Fermi Gamma-ray Space Telescope detected HE γ rays from RBS 0413 with a statistical significance of more than 9σ, a power-law photon index of 1.57 ± 0.12stat +0.11 – 0.12sys, and a γ-ray flux between 300 MeV and 300 GeV of (1.64 ± 0.43stat +0.31 – 0.22sys) × 10–5 photons m–2 s–1. We also present the results from Fermi-LAT and VERITAS, including a spectral energy distribution modeling of the γ-ray, quasi-simultaneous X-ray (Swift-XRT), ultraviolet (Swift-UVOT), and R-band optical (MDM) data. We finally 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.