Tras 30 años de carrera en el tenis, Navratilova ha tenido muchas parejas de dobles. El mayor éxito lo ha tenido con Pam Shriver, con quien ganó 20 títulos. Navratilova también ha ganado títulos con Chris Evert, Billie Jean King y Betsy Nagelsen. En dobles mixtos ha ganado con Paul McNamee, Mark Woodforde y Leander Paes. Ganó su último título de Grand Slam en dobles mixtos cuando competía con el tenista estadounidense Bob Bryan.