Desde 1989 y hasta la disolución de la Unión Soviética, fue parte de la asamblea local de Leningrado primero, donde vivió el intento de golpe de Estado de agosto de 1991, durante el cual se desvinculó de los golpistas alineándose con las autoridades soviéticas; y hasta la creación del Consejo Regional de Leningrado tras la eliminación del presídium en 1992. Se mantuvo en el Consejo Regional hasta que su participación a principios de octubre de 1993, en el golpe de octubre del 93, Fiódorov participó en el golpe contra Yeltsin: «participe directamente en el levantamiento contra Yeltsin, quien, en violación de la Constitución, dispersó el Consejo de Diputados del Pueblo». Tras ese acontecimiento, fue expulsado de la institución, que se convirtió en la Asamblea Legislativa Regional de Leningrado.
En 1993 se presentó a las elecciones a la Duma Estatal para la I Legislatura por el distrito electoral n.º 101 (Vsévolozhsk), consiguiendo el acta de diputado como miembro del Movimiento Ruso para las Reformas Democráticas (liderado por Gavríl Popov y Anatoli Sobchak). De 1993 a 1997, Fiódorov tendría una actividad notable tanto dentro de la Duma como fuera de ella al participar en varios movimientos y partidos políticos que se iban creando al punto de que en 1994 recibió una reprimenda oficial de la DUMA por estar simultáneamente en dos grupos políticos durante cuatro meses (CHP y PRES). Algunos de los grupos por los que pasó fueron: la agrupación Nueva Política Regional (NRP, de Guennadi Kalistratov), el grupo Soyuz 12 de diciembre (CHP, de liderazgo transversal), Partido de la Unidad y el Acuerdo de Rusia (PRES), el movimiento político público En apoyo de los diputados independientes (presidido por el propio Fiódorov), el grupo de diputados por la Estabilidad (grupo a favor de Chernomyrdin), el movimiento sucesor del grupo, Rusia Estable; en 1995, Rusia Estable participaría en las negociaciones que resultarían en la formación de Nuestro Hogar – Rusia (NDR), aunque la propia Rusia Estable acabaría no integrándose en el grupo para participar en las elecciones a la Duma Estatal para la II Legislatura con su propia marca.
El 17 de diciembre de 1995, en las elecciones a la Duma Estatal de la II legislatura, se postuló nuevamente para el distrito de Vsévolozhsk por el Bloque Independiente (no estaba afiliado a Rusia Estable), pero perdió ante Vladímir Grigoriev, candidato del Bloque izquierdista (Comunistas-Rusia Laborista-Por la Unión Soviética).
Entre 1996 y 2001 Evgueni Fiódorov ocupó varios puestos políticos de carácter consultivo, como el Consejo Consultivo Político de la Federación de Rusia o jefe adjunto del Departamento de Seguros del Ministerio de Finanzas (ambas instituciones creadas por Yeltsin), también llegó a ser viceministro de energía atómica (nombrado por Vladímir Putin, entonces primer ministro ruso) y miembro del presídium de la planta química OAO Kírovo-Chepetski.
El 3 y 7 de octubre de 1999 se llevó a cabo el congreso fundacional del movimiento interregional Unidad («Osos»). El 3 de octubre se nombraron los tres primeros candidatos del bloque (Serguéi Shoigú, Alexandr Karelin y Alexander Gurov) y se anunció la lista de fundadores oficiales, que incluía el movimiento «En apoyo a los votantes», presidido por Evgueni Fiódorov. El 6 de octubre se aprobaron las listas de candidatos para las elecciones a la Duma Estatal y se eligió el Consejo Coordinador del bloque de 24 personas, que incluía a Fiódorov.
El 12 de marzo de 2001, por orden del primer ministro Mijaíl Kasiánov, fue relevado de su cargo por incompatibilidad con otro puesto. Según Fiódorov, el despido se llevó a cabo ilegalmente y se produjo como resultado del conflicto entre él contra Kasiánov y Adámov sobre los temas de la privatización de empresas, aunque el resultado fue el despido tanto de Fiódorov como de Adámov.
El 1 de diciembre de 2001 en Moscú en el congreso de la coalición Unidad y Patria, creado a principios del mismo año por el partido Unidad (de Serguéi Shoigú), el movimiento Patria (de Yuri Luzhkov) y el movimiento Toda Rusia (de Mintimer Shaimíev). Como resultado de este congreso, se creó el partido Rusia Unida.
Evgueni Fiódorov, como miembro de Rusia Unida con experiencia previa de diputado, ocupó distintos cargos internos hasta la preparación de la campaña para las elecciones a la Duma Estatal para la IV Legislatura. Para las citadas elecciones, el congreso de Rusia Unida decidió que Evgueni Fiódorov, con 40 años en aquel momento, se incluyese en el grupo regional occidental (óblast de Bélgorod, óblast de Briansk, óblast de Kursk y óblast de Oriol). En su grupo regional, Fiódorov era el número cinco de la lista, después del gobernador de Oriol Yegor Stroev, el gobernador de Bélgorod Evgueni Savchenko, la diputada de la Duma Estatal Ekaterina Lajova y un cargo de OAO Oil Company LUKoil, Valeri Prozorovsky. Rusia Unida utilizó activamente la estrategia política rusa «locomotora de vapor» (atraer votantes usando candidatos semiindependientes de alto perfil), colocando en los primeros números de las listas regionales a los gobernadores.
En las elecciones a la Duma Estatal para la IV legislatura, celebradas el 7 de diciembre de 2003, realizadas con sistema mixto, la lista Rusia Unida obtuvo 37,56 % de los votos, que se materializó en 120 escaños. De estos, el grupo occidental obtuvo 4 escaños y, por lo tanto, Evgueni Fiódorov se quedó a las puertas de la Duma Estatal. Sin embargo, el 24 de diciembre se supo que 37 candidatos electos de las listas de Rusia Unida anunciaron que se negaban a ocupar sus escaños. Entre los que se negaron estaban los gobernadores Stroev y Savchenko, cuyos escaños fueron transferidos a los siguientes de la lista, Evgueni Fiódorov (5.º en la lista) y Petr Rubezhansky (6.º en la lista).
Desde 2003, Evgueni Fiódorov ha sido diputado de la Duma Estatal de la Asamblea Federal de Rusia por el partido Rusia Unida. En la IV Legislatura, fue vicepresidente del Comité de Presupuestos e Impuestos de la Duma Estatal y Comité de Política Económica, Emprendimiento y Turismo de la Duma Estatal.
En las elecciones para la V Legislatura, se presentó por la óblast de Kaliningrado siendo el segundo de la lista electoral (el primero era el gobernador regional, Georgi Boos). En estas elecciones se utilizó el sistema proporcional. Tras el recuento de votos, Rusia Unida obtuvo tres escaños por Kaliningrado, por lo que Fiódorov mantuvo su acta de diputado. Siguió trabajando en el Comité de Política Económica y Emprendimiento. También fue nombrado vicepresidente de la comisión de la Duma Estatal sobre apoyo legislativo para las actividades de entidades de monopolio natural, corporaciones estatales y organizaciones comerciales con participación estatal.
En las elecciones para la VI Legislatura, se presentó por la óblast de Rostov como octavo en la lista. Tras el recuento de votos de los comicios del 4 de diciembre de 2011, Rusia Unida obtuvo 7 diputados por Rostov, por lo que Evgueni Fiódorov no revalidaba su escaño, pero la «locomotora» de la lista, Vasili Gólubev (gobernador regional de Rostov) no tomó su acta, que fue cedida a Fiódorov.
Durante la VI Legislatura, Evgueni Fiódorov fue amenazado con ser expulsado de Rusia Unida en 2013 por no adherirse al reglamento interno del partido. En 2014, con las sanciones estadounidenses contra Rusia por el comienzo del conflicto ruso-ucraniano, propuso una ley para prohibir consultorías públicas extranjeras en Rusia. En 2015 hizo una propuesta a la presidencia de la Duma Estatal, Serguéi Narishkin, para modificar el acuerdo sobre la frontera entre Rusia y Ucrania, dado que la adhesión de Crimea por parte de Rusia dejaba sin efecto el texto vigente.[1] Antes de empezar la campaña electoral para la VII Legislatura, Fiódorov presentó 28 modificaciones a la Ley Dima Yákovlev en 2016.
Para las elecciones a la Duma Estatal para la VII Legislatura, Evgueni Fiódorov quiso presentarse a las primarias de San Petersburgo, aunque finalmente renunció a esa opción y se presentó por Kaliningrado en 2016. En el congreso preelectoral de Rusia Unida, se decidió que Fiódorov encabezaría la lista electoral por Vologda, Kaliningrado, Nóvgorod y Pskov. Rusia Unida obtendría sólo dos diputados por esta circunscripción, siendo suficiente para renovar el acta de Fiódorov.
Para las elecciones a la Duma Estatal para la VIII Legislatura en 2021 se cambió de circunscripción a la norteña Múrmansk. Inicialmente obtuvo el primer puesto en las primarias internas, aunque acabaría ocupando el segundo puesto en la lista electoral de Karelia-Múrmansk tras el gobernador de M´rumansk, Andréi Chibis. Rusia Unida sólo obtuvo un diputado por esta circunscripción, pero al haber actuado Chibis como locomotora, renunció al acta que pasó directamente a Evgueni Fiódorov, que pudo revalidar su escaño de este modo por tercera vez en su carrera política.
