En 1956, tras la independencia de Marruecos, los jugadores y directivos del Club Atlético de Tetuán (club que había sido fundado durante el Protectorado español de Marruecos) se trasladaron a la vecina ciudad de Ceuta, donde se fusionaron con la S.D. Ceuta para fundar el Club Atlético de Ceuta. El nuevo club ocupó la plaza del Club Atlético de Tetuán en la Segunda división española, donde seguiría militando durante más de una década. Su mejor clasificación fue el subcampeonato en la temporada 1960-61, lo que le permitió disputar la promoción de ascenso a Primera división, pero fue derrotado por el Elche C.F.

Descendió a Tercera división en 1968. Desde los años setenta y ochenta del siglo pasado se ha movido siempre por las categorías regionales, con un paso fugaz por Tercera División en la temporada 1977-78. En 1989 volvió a Tercera División. Su temporada más notable fue la 1993-94, en la que, de la mano de Jaco Zafrani como entrenador y Francisco Cervantes como presidente, a punto estuvo de clasificarse para los play offs de ascenso a Segunda División B. En 1995 volvió a categoría regional hasta 2006, cuando logró un nuevo ascenso a tercera división tras establecer un récord de 40 victorias consecutivas.​

En la temporada 2012/13 participa en el Grupo X de la Tercera División gracias al ascenso conseguido la temporada anterior. En esta comienza un proceso de fusión con la A.D. Ceuta, equipo que había sufrido un descenso administrativo a Tercera División en esta misma campaña por problemas económicos, siendo el motivo de esta unión la conveniencia de que solo hubiese un equipo de la ciudad ceutí en esta categoría debido, entre otros motivos, a la retirada de las ayudas económicas del Gobierno de Ceuta a los equipos profesionales de fútbol por la crisis económica y a la unión de las dos aficiones. Aunque la solución de fusión fue inviable debido a la elevada cantidad adeudada de la Asociación Deportiva, se optó por una fusión encubierta, en la que se conservó la plaza del Atlético, y se traspasaron directivos, equipo técnico y jugadores del primero a este. Se solicitó a la Federación de Fútbol de Ceuta un cambio de denominación, pero no fue aceptada para esta temporada puesto que se presentó fuera de plazo. Aun así, aunque oficialmente la plaza continuara siendo del Club Atlético de Ceuta, los dirigentes del nuevo equipo pretendían que durante esta campaña fuese conocido por los aficionados como Asociación Deportiva Atlético de Ceuta (A.D.A. Ceuta).2 Como símbolo de esta unión, el equipo cambió su clásica indumentaria de franjas rojiblancas al blanco propio de la A.D. Ceuta, así como la adopción de su escudo.3

Finalmente, en junio de 2013 se produjo el definitivo cambio de denominación del club. En un principio se barajó la posibilidad de que fuese Sociedad Deportiva Ceuta, recordando al antiguo equipo con el mismo nombre del que fue origen este club, pero a última hora se decidió que el nombre fuese Agrupación Deportiva Ceuta Fútbol Club (A.D. Ceuta F.C.). Pretendieron recuperar el nombre de la desaparecida en 1991 Agrupación Deportiva Ceuta, pero añadiéndole la coletilla F.C. por la imposibilidad de utilizar la denominación de un club que se extinguió por sus deudas.​ También se adoptó un nuevo escudo, el cual es muy similar al de la desaparecida Asociación Deportiva Ceuta con el añadido de las siglas F.C. sobre el balón que aparece en el centro.