È emerso nel 1996 a Wimbledon, quando ha superato le qualificazioni e si è spinto fino al terzo turno, dopo un'epica maratona vinta con lo spagnoloAlbert Costa. Prima del terzo turno (in cui finì poi sconfitto) disse di "voler emulare McEnroe: arrivare in semifinale quest'anno e vincere il prossimo anno". John McEnroe, infatti, alla sua prima apparizione a Wimbledon, era giunto in semifinale partendo dalle qualificazioni e l'anno dopo aveva vinto, avviando una carriera di grandi successi.
Navarra era allora molto giovane e promettente, ma la sua carriera non tenne però poi fede alle attese.
Sembrò rinascere nel 2001, quando vinse una partita in Coppa Davis contro la Finlandia, ma fu solo un lampo. Da lì in poi, più nulla.
Navarra è stato sposato per tre anni con la modella indiana Sheetal Mallar, dalla quale ha poi divorziato. Dopo il ritiro è diventato interprete di fotoromanzi.