Historia Algorytm ten, włączając jego rekurencyjne działanie, został wynaleziony około roku 1805 przez Carla Friedricha Gaussa, który używał go do interpolacji trajektorii planetoid Pallas i Juno, ale jego praca nie była powszechnie uznawana (opublikowana dopiero pośmiertnie w neo-łacinie)Gauss, Carl Friedrich, Theoria interpolationis methodo nova tractata, Werke, Band 3, s. 265–327 (Königliche Gesellschaft der Wissenschaften, Göttingen, 1866).M.T. Heideman, D.H. Johnson, C.S. Burrus, Gauss and the history of the fast Fourier transform, „IEEE ASSP Magazine”, 1(4), s. 14–21 (1984).. Jednak Gauss nie zajmował się analizą asymptotycznego czasu obliczeń. Różne ograniczone formy zostały ponownie odkryte kilka razy, zarówno w XIX w., jak i na początku XX wieku. Transformacje FFT stały się popularne po tym jak James Cooley (IBM) i John Tukey (Princeton) opublikowali w 1965 roku artykuł o ponownym wynalezieniu algorytmu i opisaniu metody na jego użycie na komputerze.