In this paper we demonstrate an all-optical switch gated by one stored photon. Using an atomic ensemble trapped inside an optical cavity, we store a photon incident transverse to the cavity in the atomic ensemble, thereby changing the state of one atom. This atom then blocks the cavity for photons incident along the cavity axis. In the regime of a classical switch, we can switch a few hundred photons with just one photon. In the regime of a quantum switch, where the stored gate photon is recovered from the medium, we can operate the switch at a photon gain of 1.4.