Martina Navratilova ir čehiete, viņas tēvs Mireks (Miroslavs) Šuberts (Mirek (Miroslav) Šubert) bija slēpošanas treneris, māte Jana Navratilova (Jana Navrátilová) nodarbojās ar tenisu un vingrošanu, vēlāk arī kļuva par slēpošanas treneri. Kad M. Navratilovai bija trīs gadi, vecāki izšķīrās, māte ar meitu pārcēlās uz Revnici. 1962. gadā māte apprecējās ar Miroslavu Navratilu (Miroslav Navrátil), kurš kļuva par pirmo M. Navratilovas tenisa treneri; viņa arī pieņēma audžutēva uzvārdu. M. Navratilovas vecāmāte Agnese Semanska (Agnes Semanska) bija tenisiste pirms Otrā pasaules kara un ieņēma otro vietu Čehoslovākijas reitingā, tenisu spēlēja arī M. Navratilovas pusbrālis Jaroslavs (Jaroslav).