Toulalan är en produkt av Nantes ungdomsakademi och gjorde sin A-lagsdebut i en vinstmatch mot Rennais under säsongen 2001/2002 där han blev inbytt. Han spelade senare även i en Uefacupenmatch innan han flyttades tillbaka till reservlaget. Under de följande två åren fick Toulalan ytterst sparsamt med speltid, men under säsongen 2004/2005 spelade han 31 matcher i ligan och blev utsedd till årets unga spelare och uttagen i årets lag av National Union of Professional Footballers.[1] Den här säsongen gjorde han även sitt enda mål för Nantes i en match mot Strasbourg som laget vann med 2–0. I maj 2006 blev det klart att Lyon värvade Toulalan. Med Lyon vann han den franska ligan både 2007 och 2008.
Den 17 juni 2011 värvades Toulalan av spanska Malaga CF för cirka 10 miljoner euro.[2]
Nantes, Frankrike
