W roku 2004 Cook wydał dwa remiksy (w czerwcu i lipcu) opartych na utworach „Happy” Maxa Sedgleya i „Follow Me Follow Me (Quem que Caguetou)” zespołu Black Alien & Speed. Ten ostatni stał się popularny w Europie po tym, jak pojawił się w reklamie Nissana X-Trail (w reklamie można usłyszeć remiks Fatboy Slima).
Po czterech latach przerwy Fatboy Slim wydał album Palookaville (w październiku 2004). Album ten zaznacza znaczącą zmianę w stylu Cooka. Zrezygnował z korzystania pętli i sampli i skupił się na bardziej konwencjonalnym kształcie utworów. W wielu przypadkach korzysta z oryginalnych nagrań na rzeczywistych instrumentach (Cook gra na gitarze basowej, Simon Thornton na wielu innych instrumentach, a czasami pojawiają się gościnnie inni artyści, np. Justin Robertson). Zmiana stylu doprowadziła także do zmian w technikach produkcji i technologii studyjnej. Przed „Palookaville” Cook korzystał z komputera Atari ST do składania utworów (komputer ten jest bardzo popularny wśród producentów muzycznych). Nowy album powstał przy użyciu zestawu Pro Tools – potężnej stacji roboczej, którą można znaleźć w najnowocześniejszych studiach nagraniowych. Ta dość niechętna zmiana została wymuszona przez konieczność dostarczenia wymaganej jakości nagrań. Projekt składa się zarówno z utworów typowych dla Fatboy Slima (jak np.