Навас се присъединява към академията на Севиля на петнадесетгодишна възраст. На 23 ноември2003 г. дебютира за мъжкия отбор в Примера дивисион, влизайки като резерва срещу Еспаньол, а до края на сезона записва още шест мача. От следващия сезон вече е в А отбора. Навас изиграва много силен сезон 2005/2006 и има голям принос за спечелването на Купата на УЕФА. През лятото на 2006 г. Севиля постига уговорка с Челси за продажбата на играча, но той отказва защото страда от хронична носталгия,[1] която по-късно е пречка и за Арсенал, чиито треньор Арсен Венгер следи Навас в продължение на две години.[2] В следващите три сезона Навас е играчът с най-много асистенции в Севиля и неизменно присъства в класацията с петдесетте най-добри играчи в Испания на списание Дон Балон. През 2007 г. отново става носител на Купата на УЕФА, а на сметката си има и две спечелени Купи на краля.