En plenos Juegos Olímpicos de Barcelona echaba a andar el Club Deportivo Lugo en la temporada de su debut en Segunda División. El técnico del ascenso, Julio Díaz, seguía al frente de una plantilla con no demasiadas novedades. Tras la disputa de la jornada 13ª el técnico de Cesuras era destituido ocupando su lugar Luis Rodríguez Vaz. El equipo siguió en la misma línea y, aunque en primavera estuvo casi un mes invicto, dos derrotas consecutivas frente a los fialiales de Real Madrid y Athletic Club lo condenaron a un descenso que se materializó al caer por un gol a cero en Palamós.
En su vuelta a la 2ªB el Club Deportivo Lugo se convirtió en un fiel representante de la clase media de la Liga. Así, entre 1994 y 2000 el equipo se clasificó en la zona tranquila de la clasificación. Sólo en la temporada 1996-1997 se rompió esta tónica cuando el grupo que dirigía Gonzalo Edrosa, con el tridente Borge-Melo-Pablo Lago como punta de lanza, dominó el Grupo I durante buena parte de la temporada. Sin embargo, dos derrotas en las últimas dos jornadas condenaron a los albivermellos a triste quinto puesto.
Con la llegada del nuevo siglo los problemas extradeportivos presidían la actividad del Club. El equipo, que no era ajeno a la situación de la entidad, estuvo a punto de perder la categoría en la temporada 2000-2001, pero una victoria en la última jornada frente al San Sebastián de los Reyes y el empate del Fuenlabrada ante el Mensajero dejó a los de Julio Díaz incluso fuera de la promoción.
Tras un noveno puesto en la 2001-2002, volvieron los malos resultados en la 2002-2003. La plantilla sufrió una gran transformación y, aunque el entrenador continuó, fue cesado tras catorce jornadas. Javier Vidales y José Luis Mosquera asumían la dirección de un equipo, que a falta de cuatro jornadas por disputarse había salido de los puestos de descenso. Desgraciadamente, las derrotas consecutivas frente a Corralejo, Alcorcón, Ponferradina y Real Madrid B llevaron a los albivermellos a 3ª División diecisiete años después.
El descenso profundizó en los problemas extradeportivos de la entidad. En esa primera temporada en 3ª tras el descenso, el equipo que dirigía Quique Prado no pasó del sexto puesto. Precisamente al acabar la temporada 2003-2004 Eliseo Corral dejaba la presidencia tras ocho años en el cargo. José Bouso le sucedía en el cargo y con el llegaba a la dirección deportiva Carlos Mouriz.
La temporada siguiente (2004-2005) comenzó con un histórico del fútbol gallego en el banquillo de las orillas del Miño: Carlos Ballesta. El equipo logró clasificarse para la promoción de ascenso al terminar tercero. Su rival en la primera eliminatoria fue el Ribadesella asturiano. La victoria en el partido de ida disputado en el Anxo Carro por tres goles a cero (obra de Braulio, Josito y Álex Velázquez) dejó prácticamente decidida la eliminatoria que se cerró con un empate sin goles a la vuelta. Sin embargo, en la 2ª eliminatoria se invirtieron los papeles. El rival, el Real Valladolid B, en una gran superioridad cerró la eliminatoria en el partido de ida disputado en el José Zorrilla venciendo por cuatro goles a uno. El 0-0 de la vuelta en Lugo dejó a los albivermellos un año más en Tercera División.
Para la temporada 2005-2006 el Club enconmendó al asturiano Juan Fidalgo el banquillo del Anxo Carro. El equipo logra con mucha suficiencia la segunda plaza aunque a una distancia considerable del campeón: el RC Deportivo B. El rival en la primera eliminatoria es nuevamente el Ribadesella. En esta ocasión la ida tuvo lugar en la localidad asturiana. Un gol de Dani Carril para el CD Lugo en el minuto 86 empató el partido a un gol dejando todo por decidirse para la vuelta. En el partido de vuelta, los goles de Pablo Martínez y Josito en la primera mitad hacían presagiar un partido tranquilo. Nada más lejos de la realidad. El cuadro asturiano logró empatar el partido en el minuto 55, pero Marcos Suárez anotaba su vigésimo gol de la temporada y permitía al CD Lugo alcanzar la siguiente eliminatoria. La Gimnástica Segoviana fue el último escollo de los de Fidalgo para el ascenso. El primer partido se disputó en el Anxo Carro. Los albivermellos fueron muy superiores hasta mediada la segunda mitad anotando tres goles e incluso errando un penalti. Un fatídico gol de Mariano para los de Segovia dejó la eliminatoria abierta para la vuelta. El 25 de junio de 2006 el CD Lugo conseguía retornar a 2ªB y lo hacía tras un partido de vuelta con muchísima tensión, Cumplidos los 90 minutos reglamentarios el marcador señalaba un gol a cero para los locales. La prolongación se convirtió en una agonía ya que un gol local dejaba a los de Fidalgo fuera. Una jugada de Moncho por banda derecha era rematada por Braulio, el rechace del portero caía en las botas del friolense Rafa Casanova que anotaba el gol del empate. Como cerraba la crónica el diario El Progreso: “A Segunda B”.
Las cuatro primeras campañas tras el retorno del Club a Segunda B acabaron con el equipo entre los diez primeros puestos de la clasificación. Juan Fidalgo, técnico del ascenso, dejó su puesto a Fonsi Valverde que tras dos temporadas (2007-08 y 2008-09) era sucedido por Quique Setién.
El santanderino comandó el equipo en la temporada 2010-2011, en la que, por primera vez en la historia, se proclamó Campeón del Grupo I de Segunda B (tras ocupar esa posición desde la jornada 17). La eliminatoria de campeones, con el ascenso en juego, deparó al Real Murcia como rival. Los goles de Chando e Isaac para los pimentoneros ponían las cosas muy difíciles para el partido de vuelta al CD Lugo. Con una entrada histórica en el Anxo Carro, los albivermellos pusieron contra las cuerdas al Murcia, pero el solitario gol de Tornero fue insuficiente, condenando al equipo a la repesca. Otro histórico, el Deportivo Alavés, fue el rival en la siguiente eliminatoria. Mendizorroza albergó un partido de ida sin apenas ocasiones de gol que concluyó con empate a cero. Con un Anxo Carro a rebosar el CD Lugo derrotó por dos goles a uno a los vitorianos. El cuadro de Setién fue mejor durante los primeros sesenta minutos pero terminó sufriendo para alcanzar la clasificación.
El último paso suele ser el más difícil y para el CD Lugo significaba eliminar al Alcoyano. En el partido de ida en tierras alicantinas, “el fútbol no fue justo” con los albivermellos que caían por un gol a cero, complicando las cosas para el partido de vuelta. En una tarde muy calurosa y con una afición totalmente entregada a su equipo, el CD Lugo encajó la única derrota como local de la temporada quedándose a las puertas del ascenso.