Leinders begann seine Karriere 1983 im Kartsport, den er bis 1993 ausübte. Mit 14 Jahren wurde er Kart-Europameister und ließ unter anderem Jarno Trulli und Ralph Firman hinter sich. 1994 wechselte er in den Formelsport und fuhr zwei Jahre in verschiedenen Formel-Ford-Rennserien. In seiner ersten Saison sicherte er sich die Meistertitel der belgischen und der Benelux Formel Ford. Ein Jahr später gewann er die britische und europäische Formel Ford. 1996 ging Leinders in der Formula Opel Euroseries an den Start und gewann erneut die Meisterschaft. Darauf wechselte der Belgier 1997 für zwei Jahre in die deutsche Formel-3-Meisterschaft. Nachdem er in seiner ersten Saison Siebter geworden war, gewann er 1998 auch den Meistertitel dieser Rennserie.
Leinders, der nun insgesamt sechs Meistertitel in Formelrennserien gewonnen hatte, gab 1998 außerdem sein Debüt in der Formel 3000. Als Teamkollege des späteren Vizemeisters Nick Heidfeld wurde er von West Competition für das letzte Rennen verpflichtet. Allerdings konnte er bei dem Rennen nicht starten. Sein erstes Rennen in der Formel 3000 bestritt er 1999 für das belgische Team Witmeur KTR, für das er zusammen mit seinem Landsmann Jeffrey Van Hooydonk an den Start ging. Leinders, der sich für sieben Rennen qualifizierte und einen Punkt holte, belegte am Saisonende den 23. Gesamtrang. 2000 wechselte Leinders zu Kid Jensen Racing. Die Saison verlief enttäuschend für Leinders, der, ohne Punkte erzielt zu haben, den 26. Gesamtrang belegte. 2001 kehrte der Belgier zu KTR zurück und bestritt seine erfolgreichste Saison in der Formel 3000. Mit zwei zweiten Plätzen als bestes Resultat belegte er am Saisonende den siebten Platz im Gesamtklassement.
2002 blieb Leinders, der die Formel 3000 in Richtung World Series by Nissan verlassen hatte, bei KTR. Mit zwei Siegen wurde er hinter Ricardo Zonta und Franck Montagny Dritter in der Gesamtwertung. 2003 blieb der Belgier in der World Series by Nissan und ging für den spanischen Rennstall Racing Engineering an den Start. Leinders wurde erneut Dritter im Gesamtklassement, diesmal hinter Montagny und Heikki Kovalainen.
2004 wurde Leinders dritter Fahrer beim Formel-1-Team Minardi. Nachdem er die Superlizenz erhalten hatte[1], durfte er ab dem zweiten Rennen der Saison in den Freitagstrainings fahren. Ein Rennen bestritt er allerdings nicht.
2005 kehrte Leinders dem Formelsport den Rücken und wechselte in die FIA-GT-Meisterschaft. Als Fahrer in der G2-Klasse wurde er von 2005 bis 2008 vier Mal Meister dieser Kategorie. 2009 startet der Belgier zum ersten Mal in der GT1-Klasse der FIA-GT-Meisterschaft.
