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.6_stat ± 0.7_syst) × 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.68_stat ± 0.30_syst. 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.12_stat ^+0.11 _{– 0.12sys}, and a γ-ray flux between 300 MeV and 300 GeV of (1.64 ± 0.43_stat ^+0.31 _{– 0.22sys}) × 10^–5photons m^–2 s^–1. We 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 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.