La victoria ante el Elche C.F, la séptima de su historia contra un equipo de Primera División en
Copa del Rey, deja a la
AD Ceuta ante la posibilidad de igualar su mejor clasificación histórica en el torneo, los cuartos de final alcanzados en la temporada 1942/1943. Para ello deberá lograr su octava victoria ante un conjunto de la máxima categoría. La primera llegó, precisamente, en 1943. Los ceutíes batieron en la ida de la primera ronda al Granada por cinco goles a cero, en el estadio
'Alfonso Murube'. Las crónicas de la época destacan la brillantez del juego de los locales, que "no encontraron rival", en el equipo Nazarí. Tavilo fue el héroe, anotando cuatro tantos. La vuelta en campo andaluz fue más complicada. El Ceuta cayó derrotado por tres goles a cero, logrando igualmente el pase a los octavos de final. Allí le tocó medirse con el Betis, que comenzaba la eliminatoria jugando en casa. A pesar de la dificultad de enfrentar a los de Heliópolis en su estadio, los de la ciudad autónoma no se encogieron, arrancando un empate a unos que dejaba las opciones abiertas para la vuelta. Las crónicas del partido destacan el "poco juego" que se vio en aquel encuentro, con los equipos "más dedicados a destruir que a buscar sus opciones". La vuelta en el 'Alfonso Murube' fue otro cantar. Los locales arrollaron al equipo bético, endosándole un cuatro a cero, con sendos dobletes de Morla y Arnau. El resultado desató la euforia en Ceuta, donde se calificó al equipo de "eminentemente copero".
El sorteo deparó un complicado enfrentamiento con el FC Barcelona en los cuartos de final, tal y como anticipaban las crónicas que hablaban de "difícil papeleta". La ida se celebró el 23 de mayo de 1943 en el campo de Les Corts. Allí el conjunto catalán no dio opción, anotando el primer tanto ya en el minuto 1. El ceutí Tavilo neutralizó la ventaja azulgrana en el minuto 3, pero en el 10, los culés volvieron a marcar y llegaron al descanso ganando 4-1. En el segundo tiempo cayó un tanto más de cada lado, para dejar un 5-2 complicado de remontar en la vuelta. "El Ceuta debe ganar al Barcelona", titulaban las previas del cacareado encuentro. Sin embargo, y a pesar del empuje de un 'Alfonso Murube' repleto, la machada fue imposible. El cuadro caballa calló estrepitosamente por dos goles a cuatro. Eso a pesar de comenzar ganando tras un gol de Morla en los instantes iniciales que abrió una ventana a la esperanza.
Pasarían más de tres décadas hasta que el Ceuta volviera a batir a un conjunto de Primera División. La siguiente víctima caballa fue el Recreativo de Huelva, en el año 1978, tras eliminar en 1/32 al Barakaldo. Las cosas no comenzaron del todo bien en la ida. En tierras onubenses se impuso el equipo local por dos goles a uno. En el 'Murube' el Ceuta venció por tres tantos a cero, pero con enorme incertidumbre, pues hasta prácticamente el minuto 80 el tanteador permanecía uno a cero, dejando al Recreativo a un único gol del pase. Tras superar al Decano del fútbol español, los caballas debían vérselas en octavos con otro equipo de la máxima categoría, el Racing de Santander. En el Sardinero venció el Ceuta, por un tanto a cero, gracias al gol anotado por Aramburu. Tras el partido, el entrenador ceutí, Jacobo Zafrani, aseguró en rueda de prensa que "incluso se pudo haber dejado sentenciada la eliminatoria en este primer partido". No fue así y en la vuelta el conjunto de la ciudad autónoma lo acabó pagando. El Racing se impuso con claridad, gracias al gol de Quique Setién en el minuto 1 y a otro de Javier García en el 63. "Se ha perdido porque no se ha jugado bien", resumió Zafrani tras el encuentro.
No tardó en esta ocasión la AD Ceuta en imponerse en encuentro contra un equipo de Primera División. Lo hizo de nuevo en la temporada 1981/1982. En esa ocasión le tocó el turno al Cádiz. Gaditanos y ceutíes se vieron las caras el 21 de octubre de 1981 en el estadio Ramón de Carranza. La escuadra local se puso dos cero con dos goles tempraneros, pero los caballas dejaron la eliminatoria abierta gracias a un gol de Luis mediada la primera parte. La vuelta en el 'Murube' vio al Ceuta ganar por dos goles a cero, con tantos de Luis y Paco Vidal. A pesar del buen rendimiento frente al Cádiz, la participación de los caballas en esa edición de la Copa del rey concluyó en la segunda ronda, tras caer derrotados por 3-2 ante el Málaga.
El Ceuta se tomaría la revancha contra el Málaga unos años después. En concreto, en la temporada 2000/2001. En un partido disputado el 13 de diciembre del año 2000 en el 'Alfonso Murube', la AD Ceuta venció por 3-2 gracias a un gol in-extremis, en el minuto 89, de Silas. En la siguiente ronda esperaba un temido Fútbol Club Barcelona, que ocupaba por aquel entonces la primera posición en la tabla de Primera División. La llegada blaugrana a Ceuta fue ampliamente celebrada y contó con una importante cobertura mediática. Con lleno absoluto en el estadio de la Ciudad Autónoma, el equipo local dio la cara, aguantando el empate a cero al descanso a un Barcelona sin Rivaldo, su principal estrella. Finalmente, dos goles de Alfonso dieron al traste con las esperanzas ceutíes. Kluivert se encargaría en los instantes finales de poner el 3-0 definitivo en el marcador.
Al año siguiente la AD Ceuta volvió a dar la campanada, logrando eliminar al Betis, que por entonces iba líder de la liga, endosándole un 4-1. Un marcador engañoso, pues el partido concluyó con empate a uno. Fue en la prórroga cuando se desató la tormenta perfecta caballa, para anotar otros tres y eliminar de la Copa al equipo presidido entonces por Manuel Ruíz de Lopera, con un jovencísimo Joaquín empezando a despuntar. El siguiente rival copero fue el Mallorca. El Ceuta soñaba con repetir machada, pero el sueño de avanzar a octavos de final se vio truncado en la tanda de penaltis, a pesar de que, según apuntan las publicaciones de la época, los jugadores ceutíes habían estado ensayando los tiros de once metros en el entrenamiento previo al partido. Los noventa minutos reglamentarios concluyeron con 0-0 y un único fallo del AD-Ceuta le condenó a la eliminación.
El conjunto caballa tendrá una nueva oportunidad de dejar en la estacada a un conjunto de primera división en la próxima ronda de Copa del Rey, tras eliminar al Elche CF. Además, de lograrlo, el club conseguiría igualar su mejor clasificación histórica en el torneo del KO.