Навара научился играть в шахматы в возрасте шести лет из книг. О его дальнейшем прогрессе позаботились отличные тренеры Людек Пахман и Властимил Янса. Навара завоевал несколько медалей на чемпионатах среди молодёжи. В 2001 году в возрасте 16 лет он набрал 7 очков из 9 партий на командном чемпионате Европы, и в следующем году, за три дня до своего 17-летия, удостоился звания гроссмейстера. В 2003 году он победил на открытом турнире — Мемориал Рубинштейна в городе Поляница Здруй (Польша).
На пятом чемпионате Европы в городе Анталья (Турция) Навара занял 6-е место, набрав 7,5 очков из 12 партий, включая ничью с чемпионом Василием Иванчуком. В 2004 и 2005 годах Навара два раза стал чемпионом Чехии.
На шахматной Олимпиаде в Турине в 2006 году Навара, играя на первой доске против сильнейших шахматистов мира набрал 8,5 очков из 12 возможных.
В 2007 году Навара впервые получил приглашение (вместо Александра Морозевича) на супертурнир «Корус» в Вейк-ан-Зее (Нидерланды). Победив Руслана Пономарева и добившись ничьей в партиях против Крамника и Топалова, Навара набрал 6,5 очков из 13 возможных и занял 7-е место.
В 2005 году в Праге Навара сыграл матч против Анатолия Карпова и в 2007 году против Бориса Гельфанда, оба матча закончились с ничейным счётом.
В 2010 г. Навара окончил Философский факультет, отделение логики Карлова университета в Праге.