Leta 2002 je zabeležila odlične rezultate in sicer četrfinale v Dohi, Estorilu, Bahii in Moskvi, polfinale v Portu, prvo zmago na WTA touru v Bratislavi, kjer je slavila tudi v dvojicah (z Nagyovo) in 3. kolo v Wimbledonu. Še posebej pomemben pa je bil nastop s Fed cup ekipo Slovenije na kvalifikacijah v Turčiji in v odločilni tekmi za uvrstitev v svetovno skupino proti Ukrajini v Portorožu. Maja je v tej seriji zabeležila šest zmag in bistveno pripomogla k dotlej največjemu ekipnemu uspehu slovenskega tenisa, ki je Sloveniji omogočil v letu 2003 tekmo proti Rusiji in v letu 2004 proti ZDA v Portorožu. V letu 2003 je z odličnimi nastopi zabeležila najvišjo uvrstitev v karieri 38. mesto med posameznicami in 34. mesto med dvojicami. Žal so se med letom začele pojavljati težave s poškodbami, tako da je sezono končala na 58. mestu. V letu 2004 je nastopila samo na Olimpijskih igrah v Atenah in dosegla zgodovinsko – prvo teniško zmago za Slovenijo na Olimpijskih igrah. Poškodba ji je preprečila boljši rezultat v nadaljevanju. Med pomembnejše zmage v karieri zagotovo sodijo zmage nad Mario Sharapovo, Svetlano Kuznecovo, Jeleno Dokič, Francesco Scavione, Flavio Penetta, Els Callens, Emanuele Gagliardi, Ano Medino Garrigues, Caro Black, Anne Kremer, Tatiano Panovo, Jeleno Kostanic, Petro Mandula, Barbaro Rittner, Jeleno Jankovic, Clariso Fernandez. Christino Torrens Valero, Vero Douchevino, Rito Grande, Dinaro Safino, Magui Serna, Lino Krasnoroutskayo, Iveto Benesovo, Marion Bartoli, Dajo Bedanovo, Eleno Bovino. Maja je po dveh operacijah na komolcu in rami, zaradi ponavljajočih se poškodb, na WTA turnirju v Portorožu v septembru 2006 zaključila profesionalno teniško kariero. V letu 2016 je ponovno zaigrala na uradnem turnirju. Udeležila se je svetovnega veteranskega prvenstva za mlajše veterane v Umagu in osvojila naslov svetovne prvakinje med posameznicami in v paru z Barbaro MULEJ med dvojicami v straostni kategoriji 35+. Po zaključku kariere se je posvetila delu z mladimi. V ta namen je ustanovila teniški klub in teniško šolo Maja Matevžič.
