* Antal matcher och mål i proffsklubbar räknas endast för de inhemska ligorna och är korrekt per den 30 november 2016. ** Antal landskamper och mål är korrekta per den 18 maj 2015.
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 UEFA cup-match 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]