Det äldsta belägget för ordet surströmming är från 1732. Surfisk nämns dock redan 1572, men mjölksyrejäsning är betydligt äldre än så. Det har gjorts arkeologiska fynd av anläggningar för fermentering i södra Sverige, som är 9000 år gamla. Mjölksyrejäst fisk har framför allt varit mycket vanlig i de norra och västra delarna av landet. Metoden har länge levt kvar i ett område som omfattar nordvästra Dalarna (gamtfisk), västra Hälsingland och södra Härjedalen och Norge (rakfisk). Det var olika slags fisk som användes för att tillverka surfisk. Längs Östersjökusten kunde det vara strömming, men i inlandet andra mindre fiskar, som mört och abborre, men också sik, öring och röding. Fisken rensades och sköljdes. Den saltades i mindre mängd salt i en tunna och täcktes med näver. Tunnan stängdes sedan med ett absolut tätt lock med tyngder på, så att en mjölksyreprocess satte igång. Surfisken kallades också gravfisk, men den har inte mycket gemensamt med vår tids gravade lax. Att den kallades gravfisk kommer av att den kunde förvaras nergrävd i marken för att hålla en jämn temperatur. Det finns också en hel del belägg för att man gjort så. Vanligt var annars att man förvarade gravfisken i ett härbre eller en sjöbod. Fisken jäste under sommaren och var färdig att ätas fram på hösten. Den syrade fisken kunde ätas som den var, precis som vi vanligtvis äter surströmming idag, men den kunde också tillagas först.
Från 1400-talet och fram till 1557 hade Gävlefiskarna rättigheten att fiska utefter norrlandskusten. Under denna tid dominerade produktionen av saltströmming. Var tionde tunna betalades till kronan/staten för arrendet. Under Gustav Vasas regeringstid blev saltet dyrare och det bidrog till att produktionen av surströmming ökade. Surströmmingen nådde sin storhetstid under 1700-talet på grund av att den utgjorde en del av provianten under de stora fältslag som pågick då.
Under 1800-talet minskade surströmmingsproduktionen kraftigt. Gävlefiskarnas privilegier hävdes 1773 och fisket utövades alltmer av lokalbefolkningen. Den vanligaste konserveringsmetoden av strömming var då åter insaltning och största delen av den surströmming som producerades avsattes lokalt.
Under 1800-talet ökade kunskapen i mikrokemi och biologi. Det medförde en gradvis förändring av sättet att framställa surströmming. Metoden att använda så kallad blodlakning tillkom. Jäsningstemperaturen ökades också från 4-6 till 15 – 18°C vilket fick till följd att jäsningstiden minskade till 8 veckor. På Ulvön var man först med att konsumentförpacka surströmming i plåtburk, omkring 1890. När en falsmaskin införskaffats blev burkarna helt täta och det blev möjligt att leverera surströmming till hela Sverige.