Mientras todo esto ocurría, miembros de la Legión y regulares llegaban gota a gota a Sevilla, sin que su escaso número fuese capaz de inclinar la balanza de forma determinante a favor de los sublevados. Yagüe, el 26 de julio, por orden de Franco, se hizo cargo del mando de la Inspección del Tercio. Se convertía así en el máximo responsable de la Legión, uniéndose a un selecto grupo de jefes legionarios integrado por Millán Astray, Franco y Valenzuela. El día 29 se hizo cargo de la Comandancia y Circunscripción Militar de Ceuta, puesto que desempeñó hasta el 7 de agosto, en que se trasladó a Sevilla.
El transporte por avión era lento y limitado, y no se podían llevar caballos, cañones ni material pesado. El 26 se preparó el cruce por barco, en el vapor Ciudad de Ceuta, de un contingente de legionarios, pero no pudieron salir por causa de que la flota republicana vigilaba, por fin, el estrecho, al tiempo que bombardeaba Ceuta. Los legionarios tuvieron que regresar el 27 a Tetuán para cruzar por aire hasta Sevilla.
Durante los primeros días de agosto legionarios de la 2ª y 4a Banderas cruzaron por avión el estrecho rumbo a Sevilla y Jerez de la Frontera para seguir a Granada. El 4 de agosto ya habían entrado en fuego: la práctica totalidad de la 2ª Legión de Yagüe bajo el mando de Castejón.
El 5 de agosto se produjo el cruce del estrecho por un gran contingente de tropas del ejército de África bajo la dirección de Franco. Esta operación ha pasado a la historia con el nombre de «Convoy de la Victoria». Fue una de las operaciones más arriesgadas de toda la Guerra Civil.
La operación fue coordinada por Yagüe —a pesar, según sostiene Garriga, de que fue uno de los que se opuso a la misma— y el capitán del Estado Mayor de la Legión, Chamorro. En la noche del 4 al 5 embarcaron mil seiscientos hombres: la 1ª Bandera de la Legión, del comandante Álvarez Entrena; el 2° Tabor de Regulares de Melilla, del comandante López Guerrero; la 1ª Batería de Artillería de Montaña del 105, mandada por el capitán Agustín Planeéis; más los hombres del Ser vicio de Automovilismo de Ejército mandados por el capitán ingeniero Correa Véglison.
El convoy partió de las costas africanas a las seis de la tarde, protegido por los aviones de Kindelán, mientras que Franco, Orgaz, Yagüe y el propio Kindelán veían desde El Hacho el desarrollo de la operación.
La expedición naval iba compuesta por las motonaves Ciudad de Algeciras[174] y Ciudad de Ceuta,[175] el carguero Arango[176] y el remolcador Benot,[177] todos bajo el mando supremo del capitán de corbeta Manuel Súnico, y con el apoyo del guardacostas Kert,[178] el cañonero Dato[179] y el torpedero 19, que salieron desde Algeciras para proteger los transportes.
Los intentos del destructor republicano Alcalá Galiano de impedir el cruce se frustraron gracias a la decidida intervención del cañonero Dato, apoyado por el guardacostas Kert, que atrajo sobre sí el fuego enemigo, entablándose un duelo de artillería entre ambos buques. Un impacto de los cañones de mayor calibre del Alcalá Galiano inutilizó la instalación eléctrica del Dato, pero su capitán siguió disparando, aunque la munición tuvo que ser subida a brazo desde el pañol por diecisiete miembros de Falange de Marruecos que habían embarcado providencialmente para reforzar la tripulación. El Alcalá Galiana estuvo a punto de abordar al carguero Arango. Llegaron a estar a escasos mil quinientos metros uno de otro, lo que permitió a la infantería que iba a bordo responder al fuego con sus ametralladoras y fusiles, llegando incluso los oficiales a ordenar calar bayonetas para rechazar un abordaje que parecía inevitable. La aparición de la aviación nacional terminó por disuadir al destructor gubernamental de sus propósitos.
Poco después llegaba el Convoy de la Victoria a la bahía de Algeciras, salvo el remolcador Benot que, excesivamente cargado por las piezas de artillería que llevaba, tuvo que regresar a Ceuta para no hundirse por el camino. Una vez desembarcaron las tropas, entró en esta bahía el acorazado republicano Jaime 1, que bombardeó la ciudad y echó a pique al Dato.[180] Pero ya era tarde, el ejército de África había cruzado el estrecho. La historia de la Legión narra este episodio de la Guerra de España de la siguiente manera:
Cerca de las costas de España, a unas cinco millas de Punta Cariñero, según. el relato del capitán de corbeta señor Súnico, apareció un destructor rojo, que salió de la Punta de Tarifa, resultando ser el Alcalá Galiana, entablándose un desigual combate, en el que el mayor poder material del barco rojo quedaba compensado por la técnica y el coraje de nuestro cañonero. Siguió el combate a rumbos paralelos próximamente y de vuelta encontrada. Desde el Arango se hizo en algunos momentos fuego de ametralladora y fusilería sobre el Alcalá Galiana, pues llegaron a estar a una distancia de poco más de mil metros. El barco pirata, al que los disparos precisos del Dato y algunas bombas de nuestra aviación habían colocado en mala situación, optó por abandonar el combate, poniendo proa a levante y amparándose para la huida en un barco que cruzaba el estrecho en aquellos precisos momentos.
Dice el comandante Súnico que el combate duró media hora y que se dispararon más de cien proyectiles. A los que íbamos en los buques de transporte [el autor de esta crónica iba en el Arango] nos pareció esta media hora un siglo.
Y sin más novedad entró todo el convoy en Algeciras, excepto el Benot, que a poco de zarpar del puerto de Ceuta se vio obligado a volver a causa de la fuerte marejada de Levante.