Ultracold atom gases provide model systems in which many-body quantum physics phenomena can be studied. Recent experiments on Fermi gases have realized a phase transition to a Fermi superfluid state with strong interparticle interactions. This system is a realization of the BCS-BEC crossover connecting the physics of BCS superconductivity and that of Bose-Einstein condensation (BEC). While many aspects of this system have been investigated, it has not yet been possible to measure the single-particle excitation spectrum, which is a fundamental property directly predicted by many-body theories. Here we show that the single-particle spectral function of the strongly interacting Fermi gas at T ~ Tc is dramatically altered in a way that is consistent with a large pairing gap. We use photoemission spectroscopy to directly probe the elementary excitations and energy dispersion in the Fermi gas of atoms. In these photoemission experiments, an rf photon ejects an atom from our strongly interacting system via a spin-flip transition to a weakly interacting state. We measure the occupied single-particle density of states for an ultracold Fermi gas of 40-potassium atoms 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. Our results probe the many-body physics in a way that could be compared to data for high-Tc superconductors. This new measurement technique for ultracold atom gases, like photoemission spectroscopy for electronic materials, directly probes low energy excitations and thus can reveal excitation gaps and/or pseudogaps. Furthermore, this technique can provide an analog to angle-resolved photoemission spectroscopy (ARPES) for probing anisotropic systems, such as atoms in optical lattice potentials.