Nel 1999 la Formula 1 arrivò in Malesia per la prima volta, in un momento in cui i primi quattro piloti della classifica erano racchiusi da soli 14 punti. Tuttavia la Malesia ospitò nel 1991 un Gran Premio di moto a Shah Alam.

Il circuito, lungo 5,542 km, è situato vicino all'aeroporto internazionale di Kuala Lumpur. Quando il paddock arrivò nel 1999 regnava l'incertezza, in quanto soltanto tre piloti avevano avuto la chance di guidare sul tracciato.

Nel primo evento Michael Schumacher tornò alle corse dal suo incidente di Silverstone di sei mesi prima. Il pilota tedesco si presentò in grande forma e tutti se ne accorsero in quanto condusse facilmente la gara prima di cedere il successo al compagno Eddie Irvine per aiutarlo nella corsa al titolo. Nel 2000 Schumacher vinse, dopo essersi aggiudicato il titolo nella gara precedente. La vittoria di fine della stagione consentì alla Ferrari di mettere le mani sulla seconda corona dei costruttori consecutiva.

Nel 2001 il GP della Malesia fu spostato all'inizio del calendario, dopo il GP d'Australia. Dunque la Malesia ospitò due corse in sei mesi e le vendite di biglietti non furono all'altezza delle speranze. Schumi s'impose per il secondo anno di seguito, ma nel 2002 fu il fratello Ralf a salire sul primo gradino del podio, si trattò dell'unica volta in tutta la stagione.

Nel 2003 Kimi Raikkonen vinse il suo primo Gran Premio in carriera, davanti a Rubens Barrichello e Fernando Alonso. Michael Schumacher subì una penalità drive-through a causa di un incidente con Jarno Trulli avvenuto al primo giro. Il tedesco finì la gara ad un deludente sesto posto.

Nel 2004 Michael Schumacher conquistò la sua terza vittoria sul circuito malese in sei anni, ma la Williams di Juan Pablo Montoya tagliò il traguardo a soli cinque secondi dalla Rossa del tedesco. Nel 2005 Fernando Alonso portò la sua Renault all'arrivo per prima davanti alla Toyota di Jarno Trulli.

Il Gran Premio 2006 della Malesia ha offerto a Giancarlo Fisichella la sua unica vittoria della stagione, vittoria che tutt'oggi rimane ancora l'ultima conquistata da un pilota italiano in Formula 1. Per ottenere questo successo, Fisichella ha tratto vantaggio da un problema di benzina incontrato dal suo compagno di squadra Fernando Alonso. Il campione in carica è comunque riuscito a recuperare e ad offrire una doppietta alla Renault, finendo davanti alla Honda di Jenson Button.

Nel 2007 Fernando Alonso ha conquistato sul tracciato malese la prima vittoria con la McLaren davanti a Hamilton e Raikkonen. Nel 2008 è stato Raikkonen ad imporsi, mentre Massa è uscito di scena in seguito ad una sbandata registrando il secondo zero consecutivo stagionale. Robert Kubica è giunto secondo anche se molto staccato dal vincitore, mentre il podio è stato completato da Heikki Kovalainen.