Jérémy Toulalan od 1998 roku trenował w szkółce juniorów FC Nantes. Od sezonu 2000/2001 był członkiem drugiej drużyny "Kanarków", natomiast szansę debiutu w pierwszym zespole otrzymał w rozgrywkach 2001/2002 podczas meczu ze Stade Rennes. Toulalan występował w nim coraz częściej i z czasem stał się podstawowym zawodnikiem francuskiego zespołu. Dla FC Nantes Toulalan przez pięć sezonów rozegrał łącznie 94 ligowe pojedynki i zdobył jedną bramkę. Latem 2006 roku francuski pomocnik za siedem milionów euro trafił do Olympique Lyon. Miał zastąpić tam Mahamadou Diarrę, który odszedł do Realu Madryt. W nowym klubie Toulalan od razu wywalczył sobie miejsce w wyjściowej jedenastce i w debiutanckim sezonie rozegrał 30 spotkań w Ligue 1. W dużym stopniu przyczynił się do wywalczenia przez swoją drużynę szóstego w historii klubu tytułu mistrza kraju. W sezonie 2007/2008 Lyon ponownie zakończył ligowe rozgrywki na pierwszym miejscu, a Toulalan zajął trzecie miejsce w plebiscycie na najlepszego piłkarza sezonu. Został wyprzedzony tylko przez króla strzelców ligi - Karima Benzemę oraz Senegalczyka Mamadou Nianga.