Fue un verdadero desacierto del rey Fernando el Católico nombrar para la empresa dos celebridadesde tan opuestos caracteres, pues ni la educación, ni las aptitudes, ni las miras de uno y otro estuvieron jamás acordes. Ya antes de embarcarse las tropas en Cartagena estalló la disensión entre Navarro y el cardenal.

La flota zarpó el 16 de mayo de 1509. Estaba formaba de 90 naves de diferentes clases para el transporte de la tropa, la artillería y el abundante aprovisionamiento necesario. Al día siguiente la flota llegó a Mazalquivir después de anochecido. Orán se halla a un tiro de piedra de Mazalquivir, situada con una llanura al norte y una áspera sierra al sur, que se dirige en pendiente hacia Mazalquivir. Tenía una muralla robusta y dos castillos, de manera que podía defenderse con una guarnición pequeña. Con ocasión de la llegada de los cristianos se reunieron unos 10.000 moros en la cumbre de la sierra para reforzar las tropas de la plaza y detener el avance de los cristianos.

La infantería española desembarcó antes del amanecer del día siguiente. La caballería y la artillería tardaron algo más. Pedro Navarro emplazó seis piezas de artillería y con sus fuegos apoyó el avance de los españoles, que comenzaron a subir la sierra después del mediodía. Iban divididos en cuatro columnas y sin detenerse por la lluvia de piedras, saetas y balas que disparaban los moros, llegaron a la cumbre antes de anochecida.

Con una de las columnas, Pedro Navarro desalojó a los moros de las alturas inmediatas a Orán. Las otras tres llegaron al pie de los muros de la ciudad y procedieron a asaltarla ayudados de picas y escalas. El capitán Sosa, de la guardia del cardenal, fue el primero en escalar las murallas. Bernardino de Meneses, al frente de los soldados reclutados en Talavera, conquistó una de las puertas de la ciudad. Algunos españoles entraron por la puerta del mar. Los moros no pudieron resistir el empuje de los españoles, y comenzaron a huir, tras sufrir numerosas bajas. Los supervivientes fueron hechos cautivos. Pedro Navarro hizo a los moros más de 4.000 bajas y 8.000 prisioneros, siendo muy escasas las pérdidas españolas al conquistar la ciudad.

El cardenal Cisneros no asistió al asalto, pues los soldados se lo impidieron debido a su edad, ya que contaba entonces con 73 años. El dia 18, después de haber tomado la plaza, el cardenal Cisneros entró en la ciudad procedente de Mazalquivir entre aclamaciones de los soldados y colocó la Santa Cruz en las murallas de la ciudadela. No obstante, Pedro Navarro continuó con su actitud hostil hacia el cardenal, al cual llegó a decirle que:

"Tan mal está un ejército con dos generales como lo estaría una persona con dos cabezas." ... "Debeis volver a vuestro arzobispado a recibir los aplausos por vuestra victoria de Orán; de hoy más no se dará aquí un paso sino a nombre del rey y bajo mi conducta, que yo se mandar soldados como vos sabeis apacentar las ovejas en vuestra diócesis, que están sin pastor; y de este modo cada uno hará su oficio. Ved vos que tal arzobispo haría yo, y juzgad que tal general sereis vos."

El cardenal se convenció de que debía regresar a España, cosa que hizo en una galera. Desembarcó en Cartagena para dirigirse a la Corte y decir allí que aquellos mares estaban por fin libres de peligros gracias a sus desvelos.