Astronomers are often interested in detecting periodic signals in noisy time-series data. The Lomb-Scargle periodogram was designed for this purpose, and can efficiently handle complications like irregular sampling and heteroskedastic measurement errors. However, many signals in astronomy are non-sinusoidal, and while extensions to the Lomb-Scargle periodogram are able to handle a variety of waveform shapes, this comes at the cost of decreased sensitivity. Template fitting algorithms provide better sensitivity by explicitly fitting a fixed-shape waveform to the data, but this is too computationally demanding to be practical for large surveys. We present a new algorithm, the Fast Template Periodogram, that combines the speed advantage of Lomb-Scargle with the sensitivity of template fitting. The Fast Template Periodogram provides up to 4 orders of magnitude of speedup over more naive template fitting methods for large surveys with greater than 1,000 datapoints per object.