The Fast Template Periodogram extends the Generalised Lomb Scargle periodogram (Zechmeister and Kurster 2009) for arbitrary (periodic) signal shapes. A template is first approximated by a truncated Fourier series of length H. The Nonequispaced Fast Fourier Transform NFFT is used to efficiently compute frequency-dependent sums. Template fitting can now be done in NlogN time, improving existing algorithms by an order of magnitude for even small datasets. The FTP can be used in conjunction with gradient descent to accelerate a non-linear model fit, or be used in place of the multi-harmonic periodogram for non-sinusoidal signals with a priori known shapes.