Entre 2002 et 2004, il est membre du conseil régional des Jeunesses socialistes d'Andalousie et secrétaire de l'organisation dans la commune de Bailén. Il se porte candidat à la huitième position sur la liste présentée par le parti dans la circonscription autonomique de Jaén et conduite par Mar Moreno lors des élections andalouses de [2]. Avec 222 596 voix, la liste obtient sept des douze sièges en jeu et Felipe Sicilia n'est pas élu[3]. Il fait néanmoins son entrée au Parlement d'Andalousie en à la suite de la démission de Carmen Peñalver, élue maire de Jaén au mois de précédent[4]. Secrétaire de la commission du Suivi et du Contrôle du financement des partis politiques, il est membre de la commission de l'Environnement, de la commission de l'Égalité et du Bien-être social et de celle de l'Éducation.
Il conserve sa position lors du scrutin régional de [5] mais se voit contraint de quitter le Parlement andalou car la liste ne remporte que sept sièges[6]. Il retrouve son mandat en après la démission de Gaspar Zarrías, nommé secrétaire d'État à la Coopération par le nouveau ministre de la Politique territoriale, Manuel Chaves[7]. Sicilia siège notamment à la commission de l'Emploi dont il est secrétaire et à la commission de l'Agriculture et de la Pêche de laquelle il est porte-parole.
Il est élu conseiller municipal de Bailén lors des élections locales de . Il est chargé par le maire de gérer le domaine de l'Économie et des Finances jusqu'aux élections suivantes de .
Député national
Lors des élections générales de , il postule en troisième position sur la liste investie par le parti dans la circonscription de Jaén, derrière Concha Gutiérrez et Zarrías[8]. Il se trouve élu au Congrès des députés après que la liste a obtenu les trois sièges nécessaires. Membre de la commission des Budgets et porte-parole adjoint à la commission de l'Agriculture, de l'Alimentation et de l'Environnement pendant toute la durée de la législature, il devient porte-parole adjoint à la commission de l'Intérieur en .
Il est remonté à la deuxième place sur la liste conduite par la présidente fédérale du PSOE, Micaela Navarro, pour les élections législatives de [9]. Réélu au palais des Cortes, il est promu porte-parole titulaire de la commission de l'Agriculture, de l'Alimentation et de l'Environnement et intègre comme simple membre les commissions de l'Intérieur, des Budgets et de la Sécurité routière. Il conserve son mandat parlementaire après la tenue du scrutin anticipé de [10] et est confirmé dans l'ensemble de ses responsabilités parlementaires.
Député andalou, il soutient Susana Díaz — secrétaire générale de la puissante fédération socialiste andalouse — lorsque celle-ci se présente lors du 39e congrès fédéral du parti face à l'ancien titulaire Pedro Sánchez, déposé par les « barons territoriaux » du parti, et au député de BiscayePatxi López. Après la facile victoire de Sánchez et la cuisante défaite de Díaz qui bénéficiait pourtant de l'appui de l'appareil du parti, Sánchez nomme une nouvelle direction du groupe parlementaire — majoritairement composé de députés favorables à Díaz — intégrant les différentes sensibilités et dans laquelle Sicilia est nommé secrétaire adjoint sous les ordres du secrétaire général Rafael Simancas et de la porte-parole Margarita Robles[11],[12]. À ce titre, il devient membre titulaire de la députation permanente, porte-parole adjoint de la Junte des porte-paroles et membre de la commission du Règlement. Il est, en outre, vice-président de la délégation espagnole au groupe chargé du Contrôle parlementaire conjoint d'Europol et membre suppléant de la délégation espagnole à l'Assemblée parlementaire du Conseil de l'Europe.
Pressenti comme un potentiel candidat à la succession de Susana Díaz, il plaide en pour un changement à la tête du PSOE d'Andalousie et pointe le fait que l'ancienne présidente de la Junte et secrétaire générale de la fédération andalouse représente un « projet épuisé » qui a besoin d'un « stimulant »[13].