U februaru 1996, bend je debitovao sa muzičkom kućom Creation

U februaru 1996, bend je debitovao sa muzičkom kućom Creation, “Hometown Unicorn” je postao New Musical Express singl nedelje, po izboru gledalaca Pulp-a, a prvi singl SFA koji je dospeo na UK Top 50, našao se na 47. mestu.Ponovim snimanjem pesme “God! Show Me Magic!”, dospeli su do 33. mesta, pesma je puštena u aprilu 1996 i postala je NME singl nedelje. U maju, su objavili svoj debi album Fuzzy Logic, ponovo sa raznim kritikama. Prodaja je bila spora, iako se album popeo na 23. mesto na top listama, ali je ipak posle toga dobio malo više interesovanja kada je izašao sledeći singl “Something 4 the Weekend” (prerađen, u više verzija na albumu) emitovanjem na radiju dostigao je 18. mesto u julu 1996. Singl sa albuma, “If You Don’t Want Me to Destroy You” je imao kao podršku numeru pod nazivom “The Man Don’t Give a Fuck”. Međutim, bilo je problema u kliringu uzorka od “Showbiz Kids” od Steely Dan koja formira osnovu hora, to je bilo za drugačiju numeru. Singl je bio na 18. mestu. Međutim, SFA pesmu “The Man Don’t Give a Fuck” smatraju kao jednu od svojih najboljih pesama do sada i bore se za jasno uzorak pesme. Kad su to uspeli, nisu imali novo izdanje kome bi priključili ovu pesmu- tako da je pesma izašla kao singl u ograničenom izdanju sa svojim pravima, u decembru 1996. Ovo je rezultovalo da SFA uspostavesvoj legendarni status kao kultni heroji, pošto pesma sadrži reč “jebote” preko 50 puta nije bilaskoro nikad puštana. pesma je zauzela 22. mesto ne top listama I taj broj je postao SFA standardni broj zatvaranja, kada sviraju uživo.