Ultracold atomic gases provide model systems in which to study many-body quantum physics. Recent experiments using Fermi gases have demonstrated a phase transition to a superfluid state with strong interparticle interactions. This system provides a realization of the 'BCS-BEC crossover' connecting the physics of Bardeen-Cooper-Schrieffer (BCS) superconductivity with that of Bose-Einstein condensates (BECs). Although many aspects of this system have been investigated, it has not yet been possible to measure the single-particle excitation spectrum (a fundamental property directly predicted by many-body theories). Here we use photoemission spectroscopy to directly probe the elementary excitations and energy dispersion in a strongly interacting Fermi gas of 40K atoms. In the experiments, a radio-frequency photon ejects an atom from the strongly interacting system by means of a spin-flip transition to a weakly interacting state. We measure the occupied density of single-particle states at the cusp of the BCS-BEC crossover and on the BEC side of the crossover, and compare these results to that for a nearly ideal Fermi gas. We show that, near the critical temperature, the single-particle spectral function is dramatically altered in a way that is consistent with a large pairing gap. Our results probe the many-body physics in a way that could be compared to data for the high-transition-temperature superconductors. As in photoemission spectroscopy for electronic materials, our measurement technique for ultracold atomic gases directly probes low-energy excitations and thus can reveal excitation gaps and/or pseudogaps. Furthermore, this technique can provide an analogue of angle-resolved photoemission spectroscopy for probing anisotropic systems, such as atoms in optical lattice potentials.