Motivated by recent numerical studies of Ag on Pt(111), we derive an expression for the RKKY interaction mediated by surface states, considering the effect of anisotropy in the Fermi edge. Our analysis is based on a stationary phase approximation. The main contribution to the interaction comes from electrons whose Fermi velocity vF is parallel to the vector R connecting the interacting adatoms; we show that, in general, the corresponding Fermi wave vector kF is not parallel to R. The interaction is oscillatory; the amplitude and wavelength of oscillations have angular dependence arising from the anisotropy of the surface-state band structure. The wavelength, in particular, is determined by the projection of this kF (corresponding to vF) onto the direction of R. Our analysis is easily generalized to other systems. For Ag on Pt(111), our results indicate that the RKKY interaction between pairs of adatoms should be nearly isotropic and so cannot account for the anisotropy found in the studies motivating our work. However, for metals with surface-state dispersions similar to Be(10¯10), we show that the RKKY interaction should have considerable anisotropy.