1956. október 18-án született Prágában Martina Subertova néven. Szülei válása után mostohaapja, Miroslav Navratil nevét vette fel, aki később első edzője is lett. Nyolcévesen döntötte el, hogy profi teniszjátékos lesz, tizenöt évesen nyerte meg hazája bajnokságát. Egy év múlva a profik között is bemutatkozott, első külföldi tornagyőzelmét a Florida állambeli Orlandóban szerezte meg.

1975-ben már két Grand Slam-tornán is döntőt játszhatott, de mindkétszer kikapott: Ausztráliában a hazai Evonne Goolagong, a Roland Garroson pedig az amerikai Chris Evert verte meg. Neve abban az évben lett világszerte ismert, de még nem a játéka miatt. Az amerikai bajnokság elvesztett elődöntője után, nemzetközi sajtótájékoztatón közölte: politikai menedékjogot kért az Egyesült Államokban. Az egyre sikeresebb tizenéves nem viselte el, hogy a hazai kommunista hivatalnokok előírták neki, melyik versenyen induljon, kivel barátkozzon, ráadásul tekintélyes summát vontak le nyereményeiből. A pohár akkor telt be, amikor fegyelmi meghallgatásra rendelték haza, mert engedély nélkül indult egy tornán. Az amerikai állampolgárságot 1981-ben szerezte meg, cseh állampolgárságát 2008-ban kapta vissza.

Első nagy tornagyőzelmét 1978-ban Wimbledonban szerezte, a fináléban Chris Evertet győzte le, és átvette a vezetést a világranglistán is, címét egy évvel később, ugyancsak Evert ellenében sikerült megvédenie. A nyolcvanas évek elején győzedelmeskedett Ausztráliában, a Roland Garroson és Wimbledonban is, az US Open döntőjében azonban döntő szett rövidítésben szenvedett vereséget Tracy Austintól.

Agresszív stílusával, gyorsaságával és rendkívüli testi adottságaival emelkedett ki a mezőnyből. Balkezes szerva-röpte játéka ellen nehezen találták a megfelelő taktikát az ellenfelek. 1983-as mérlege a mai napig hihetetlen: 86 mérkőzést nyert meg, és mindössze egyet veszített el, 1982 és 1984 között pedig csak hat mérkőzés után távozott vesztesként.

1984-ben sikerült megvalósítania minden teniszező álmát, a Grand Slamet, vagyis mind a négy nagy tornán diadalmaskodott, amit még két elsőséggel toldott meg, így egymás után hat nagy bajnokságon győzedelmeskedett. Párosban is halmozta a sikereket, Pam Shiverrel az oldalán sorozatban nyerte a tornákat. 1983 és 1985 között 109 mérkőzésen maradtak veretlenek, Navratilova 1985-ben Temesvári Andreával az oldalán győzedelmeskedett a Roland Garroson. 1985 és 1987 között további hat Grand Slam-győzelemmel gazdagodott, Wimbledonban 1982 és 1987 között hat éven át nem talált legyőzőre, ilyen sorozatra az open-érában sem azelőtt, sem azóta, sem a férfiak, sem a nők között nem volt példa.

1987-ben aztán feltűnt a színen az ifjú német Steffi Graf, aki a francia nyílt bajnokság fináléjában megverte Navratilovát. A sportág következő éveit kettejük párharca határozta meg: Graf 1988-ban és 1989-ben is felülmúlta a wimbledoni döntőben a cseh-amerikai játékost, aki 1990-ben aratta utolsó Grand Slam-győzelmét egyesben, az általa olyannyira szeretett wimbledoni tornán. 1991-ben még döntőt játszhatott az amerikai nyílt bajnokságon, az elődöntőben megverte Grafot, a fináléban azonban kapitulálnia kellett Szeles Mónika előtt. Három évvel később, csaknem 38 évesen még egyszer finalista volt Wimbledonban, ahol Conchita Martineztől szenvedett vereséget.

1994-ben bejelentette visszavonulását, ezután már felvállalta szexuális irányultságát: kezdetben biszexuálisnak, később leszbikusnak vallotta magát. Életrajzi könyvében nyíltan beszélt e témáról, szerelmi életéről, egyes játékostársai iránt érzett vonzalmáról. Számtalan esetben vett részt melegjogi kezdeményezésekben, amiért kitüntetésben is részesült. Politikai témákban is hallatja szavát, jótékonykodik, alapítványokat támogat. 2009 óta egy orosz üzletasszonnyal él együtt, aki 1991-ben szovjet szépségkirálynő volt, 2014-ben összeházasodtak.

Navratilova 2000-ben újból teniszütőt ragadott, s főként páros versenyeken indult. 2003-ban vegyes párosban megnyerte Wimbledont, ezzel Billie Jean King társaságában az egyetlen húszszoros bajnok lett. Pályafutása végére 2006-ban az amerikai bajnokságon vegyes párosban aratott győzelmével tett pontot, ezzel - csaknem ötvenévesen - ő lett a legidősebb játékos, aki valaha Grand Slam-győzelmet szerzett.

A tenisz élő legendája Grand Slam-tornákon 59 győzelmet aratott (18 alkalommal egyéniben, 31-szer párosban, 10-szer vegyes párosban), ezzel az örökranglistán a 62-szeres győztes Margaret Court mögött a második helyen áll. A hivatalos világbajnoki címet háromszor (1979, 1982, 1983) szerezte meg, ugyancsak háromszor volt Mesterek Tornája győztes (1982, 1984, 1986), a világranglistát 331 hétig vezette. Egyéniben, párosban és vegyes párosban is megcsinálta a karrier Grand Slamet, ez rajta kívül csak két teniszezőnek sikerült. Pályafutása során egyéniben 167, párosban 177 tornát nyert, mindkettő rekord a teljes (férfi és női) mezőnyben. Ő tartja a sorozatban megnyert meccsek rekordját is (74), összesen 1442 mérkőzést vívott, és csak 219-et veszített el, ami 86,6 százalékos mutató. 2000-ben a Tenisz Hírességeinek Csarnokába választották, a szakírók többsége Steffi Graf társaságában a világ legjobb teniszezőjeként tartja számon.