De Staat was oorspronkelijk een soloproject van Torre Florim. Hij nam thuis het album Wait for evolution op, waarbij hij soms de hulp inriep van Emil van Steenwijk, die beter bekend is onder zijn alter egoFuck The Writer, en Wout Kemkens van The Bloody Honkies.[1] Om de nummers live goed ten gehore te kunnen brengen, formeerde Florim een liveband, waarmee hij veel optrad. In februari 2008 maakte Florim bekend dat het album af was, maar dat de release werd uitgesteld, omdat er interesse was van een platenlabel.[1] Op 16 juli2008 maakte hij bekend dat het album uitgegeven zou gaan worden door Excelsior Recordings. Voor het album zou gaan verschijnen werd het echter eerst opnieuw gemixt en gemasterd door huisproducerFrans Hagenaars.[2] In oktober van dat jaar speelde De Staat driemaal in Engeland in het voorprogramma van dEUS, om vervolgens een tijd als voorprogramma te spelen bij zZz.[3]
Op 8 januari2009 werd het album Wait for evolution gepresenteerd in DoornroosjeNijmegen. Op 9 januari verscheen het officieel in de winkel. Het album kreeg goede kritieken en stond uiteindelijk 23 weken in de Album top 100, waarbij het in de eerste week op de 13e plaats binnenkwam. Als eerste promosingle werd gekozen voor het nummer The fantastic journey of the underground man, waar een videoclip bij werd gemaakt, die regelmatig te zien was op TMF.[4] Het merendeel van de nummers gaat over thema vrijheid.[4] Het succes van de plaat zorgde ervoor dat hij op 2 maart werd uitgegeven op vinyl en op 9 maart werd uitgebracht in België.[5] Na de uitgave van de plaat speelde de band zowel op Pinkpop, Parkpop als Lowlands.[6] Het nummer The fanstastic journey of the underground man werd gebruikt in het computerspelColin McRae: DiRT 2. Op 28 juli bracht de band een ep uit rond het nummer Habibi, dat voor deze ep opnieuw werd opgenomen. De ep werd enkel online aangeboden.[7] Op 11 september kreeg De Staat de 3voor12 Award uitgereikt voor het album Wait for evolution. Op 26 oktober2009 maakte de band bekend dat ze nog een live-dvd zou uitbrengen van hun set op Lowlands en vervolgens gingen werken aan hun tweede album.[8]