2004: Inolvidable

En el 2004 llega al equipo Omar Sebastian Perez, en su primera experiencia en Colombia y sin gran cartel, comandando al equipo hacia el quinto campeonato de la Primera A, teniendo como técnico a Miguel Ángel “El Zurdo” López. Además, ese mismo año participa en su primera Copa Sudamericana En la eliminatoria colombiana jugó contra Millonarios de Bogota, perdiendo el primer partido 1-0 en Bogota y ganando 2-0 en Barranquilla logrando un resultado global de 2-1. En los octavos de final se enfrenta al ganador de la eliminatoria peruana:Alianza Atlético de Sullana. Junior vence de nuevo en los dos partidos 2-0 en Sullana y 4-1 en Barranquilla para un resultado global de 6-1. Junior clasifica a los Cuartos de Final para enfrentar a Internacional de Brasil. Junior pierde 1-0 en Porto Alegre y empata 1-1 en Barranquilla.

Quinta estrella

En el Torneo Apertura 2004, Junior termina quinto con 30 puntos, clasificando a los Cuadrangulares Semifinales. En los cuadrangulares, Junior queda ubicado en el grupo A junto a Nacional, América y Pasto. Junior termina último con 6 puntos. En el Torneo Finalización, Junior clasifica a los cuadrangulares semifinales, octavo con 28 puntos. Queda ubicado en el grupo B junto a Deportivo Cali, Independiente Medellin y Atletico Bucaramanga, clasificando a la final con 13 puntos (5 más que el Deportivo Cali). En la Final, Junior enfrenta a Atlético Nacional. En el partido de Barranquilla, Junior vence 3-0. En el partido de Medellín, Nacional vence a Junior 5-2, quedando un resultado global de 5-5 y obligando a la serie de penales en donde Junior vence 5-4. Junior así obtenía su quinto título nacional y su novena clasificación a Copa Libertadores. También Junior fue campeón del torneo amistoso Copa Cotton USA, realizada en Medellin como homenaje a los 10 años de la muerte de Andrés Escobar.

Alineación: Luis Fernández, Roberto Peñalosa,Walter Ribonetto, Hayder Palacio, Cesar Fawcett, Jose Amaya, Juan Carlos Quintero, Leonardo Rojano, Omar Sebastian Perez, Orlando Ballesteros, Martín Arzuaga.   DT: Miguel Angel Lopez

Suplentes:  Carlos Perez, Jorge Amara, Freddy Arrieta, Daniel Machacón, Wilson Carpintero 

Copa Libertadores (2005)

En el 2005 participa en su novena Copa Libertadores. En la fase preliminar enfrenta a Oriente Petrolero de Bolivia, ganando con un resultado global de 5-2. Luego integró el grupo 5 enfrentándose a clubes como River Plate de Argentina, Nacional de Uruguay y Olmedo de Ecuador. Quedó segundo del grupo detrás de River Plate, clasificando a los Octavos de Final, donde enfrentó a Boca Juniors de. En esta serie, el partido de Barranquilla terminó 3-3 y el de Buenos Aires terminó 4-0, quedando eliminado de la competición

En el Torneo Apertura, Junior termina décimo con 25 puntos. Al acabar este torneo sale del equipo Omar Sebastian Perez. En el Torneo Finalización, Junior terminó quinto con 29 puntos, clasificando a los cuadrangulares semifinales. En esa instancia, queda en el grupo A junto a Deportivo Cali, Once Caldas y América,  terminando segundo con 10 puntos (1 menos que el líder Deportivo Cali) quedando eliminado del torneo. Al final del año salieron del equipo, Martín Arzuaga y Macnelly Torres.

(2006) – (2008): La debacle

Para el Torneo Apertura 2006 vuelve al equipo el histórico Victor Danilo Pacheco. En ese certamen, Junior termina 16°, haciendo una de sus peores campañas de la historia con 17 puntos, quedando eliminado del torneo. Para el Torneo Finalización vuelve el argentino Omar Sebastian Pérez (procedente de Mexico) y el máximo goleador del equipo en su historia: Ivan René Valenciano, Víctor Danilo Pacheco sale. Junior terminó 15 con 17 puntos, quedando eliminado del torneo.​ A final de año salen Hayder Palacio e Ivan René Valenciano.

Para el Torneo Apertura de 2007 llegó al equipo el entonces desconocido Teófilo Gutiérrez, pero la gran contratación del equipo fue el argentino Gabriel Fernández. En este torneo, Junior termina 11 con 23 puntos, quedando eliminado del certamen. A mitad de año se van Gabriel Fernández y Omar Sebastian Perez. Para el Torneo Finalización llega Carlos Valderrama como director deportivo del equipo, Junior termina 13 con 18 puntos, quedando eliminado del certamen.

A principios de 2008 Junior se vio amenazado por el descenso por lo que contrató a Giovanni Hernandez como principal contratación, y trajo de vuelta a Hayder Palacio (quién había jugado el último año en el Deportivo Cali) para el Torneo Apertura. En este torneo, Junior termina 12 con 24 puntos, quedando eliminado. En la Copa Colombia termina líder del grupo A con 20 puntos, 1 más que el Union Magdalena, clasificándose a la segunda fase. Martín Arzuaga volvió al equipo para el segundo semestre.En el Torneo Finalización, Junior termina segundo con 31 puntos (dos menos que el líder Deportes Tolima) clasificando a los cuadrangulares semifinales después de dos años y medio. En los Cuadrangulares Semifinales, Junior quedó en el grupo B junto a America, Pereira y Deportivo Cali, terminando tercero con 7 puntos y quedando eliminado del torneo.​ En la Copa Colombia Junior quedaría eliminado en segunda fase a manos de Envigado al perder 1-0 en Envigado y ganar 3-2 en Barranquilla, clasificando Envigado por mayor cantidad de goles de visitante. A final de año Martin Arzuaga sale del equipo.Subcampeón apertura (2009-I)Para el Torneo Apertura 2009 llegan Ricardo Ciciliano y Adrian Berbia como principales contrataciones. En este torneo, Junior termina segundo con 31 puntos (1 menos que el líder Deportes Tolima), clasificando a los cuadrangulares semifinales donde queda ubicado en el grupo B junto a Deportivo Cali, Envigado F.C. y Cúcuta Deportivo, terminando líder con 9 puntos (los mismos que el Deportivo Cali que se vio perjudicado al quedar Junior en mejor posición en la fase Todos contra Todos) clasificando a la final. En la final, Junior enfrenta a Once Caldas. Junior pierde los dos partidos 2-1 en Manizales y 1-3 en Barranquilla. Así, Junior conseguiría su sexto subcampeonato. Teófilo Gutiérrez es goleador del Torneo Apertura con 16 goles. Mientras, en Copa Colombia, Junior termina 2° del grupo A con 21 puntos (1 menos que el líder Atlético de la Sabana), clasificando a la segunda fase del torneo.

Para el Torneo Finalización, Junior contrata al experimentado volante Freddy “Totono” Grisales. Junior termina sexto con 27 puntos (11 menos que el líder Independiente Medellin, clasificando a los cuadrangulares semifinales, donde después del sorteo queda ubicado en el grupo A junto a Independiente Medellín, Deportivo Pereira y Real Cartagena. Junior termina segundo con 9 puntos, 5 menos que el líder Independiente Medellín, quedando eliminado del torneo. Sin embargo, Junior consigue el tercer cupo colombiano a la Copa Libertadores al ser el equipo que más puntos logró en el año (76) superando por dos puntos al Deportes Tolima.

En la Copa Colombia, Junior enfrenta a Medellin, eliminándolo con un global de 3-2 (3-1 en Barranquilla y 1-0 en Medellin), clasificando a la tercera fase, donde enfrentaría al Quindío, empatando 0-0 en Armenia y 2-2 en Barranquilla. Desde los penales clasifica Junior a semifinales, donde enfrentará a Pasto, perdiendo ambos partidos 3-1 y 1-2 en Pasto y Barranquilla respectivamente, quedando eliminados. Carlos Bacca logra coronarse goleador de la Copa Colombia con 11 goles, 4 más que su más cercano perseguidor Jorge Enrique Vargas (Atlético de la Sabana).

A pesar de haber logrado la clasificación a Copa Libertadores como equipo con más puntos cosechados durante 2009, el técnico Julio Comesaña es despedido, siendo sustituido por Diego Edison Umaña. Al final del año salen del equipo Teófilo Gutierrez (rumbo al fútbol turco) y Camilo Ceballos y se retira Dumar Rueda, siendo estas las principales bajas del equipo para el siguiente torneo.