The fast multipole method (FMM) was originally developed for perfect electric conductors (PECs) in free space, through exploitation of spectral properties of the free-space Green's function. In the work reported here, the FMM is modified, for scattering from an arbitrary three-dimensional (3-D) PEC target above or buried in a lossy hall space. The "near" terms in the FMM are handled via the original method-of-moments (MoM) analysis, wherein the half-space Green's function is evaluated efficiently and rigorously through application of the method of complex images. The "far" FMM interactions, which employ a clustering of expansion and testing functions, utilize an approximation to the Green's function dyadic via real image sources anal far-field reflection dyadics. The half-space FMM algorithm is validated through comparison with results computed via a rigorous MoM analysis. Further, a detailed comparison is performed on the memory and computational requirements of the MoM and FMM algor ithms for a target in the vicinity of a half-space interface.