La parroquia tiene su origen en una ermita que desde 1567 existía en este lugar, llamada de San Antonio de los Portugueses. En las dependencias anejas, propiedad de una noble dama portuguesa -de ahí muy probablemente la primitiva advocación de la ermita- se alojaron un grupo de mujeres que, llevando una vida de piedad, fueron el germen del convento de monjas agustinas de nuestra ciudad, ya desaparecido, que se encontraba en la actual plaza de Candelaria.
Por iniciativa del obispo Antonio Zapata, estas mujeres se trasladan en 1593 a la que sería su nueva morada, el convento de la Candelaria. Tras su marcha, la Cofradía de los Morenos se estableció en su lugar, pasando a denominarse ermita del Rosario, por la devoción a esta advocación que tenía la cofradía y a la imagen que allí se ubicó.
La ermita tendría una disposición paralela a la actual calle Rosario. Posteriormente las reformas cambiaron su orientación, dándole un giro de noventa grados y haciéndola perpendicular a la calle. El templo tuvo su primera gran reforma a principios del siglo XVIII, cuando se convierte en una iglesia de una nave, con mayor entidad que la ermita que había sido hasta entonces. De esa reforma queda la portada de mármoles genoveses.
Aunque no fue párroco, es obligado recordar la figura del sacerdote José Sáenz de Santamaría, Marqués de Valde-Íñigo. Fue un gran benefactor de la parroquia gracias a su celo apostólico y cuantiosa fortuna -recibida por herencia-, ya que buena parte de ella la dedicó a enriquecer la iglesia, llegando a comprar varios terrenos contiguos al templo para su ampliación. Gracias a ello, a finales del XVIII, Torcuato Benjumeda se encarga de una profunda reforma del templo, añadiendo dos naves laterales, y estando al frente, como arquitecto de retablos, de un auténtico programa que contemplaba la decoración integra de la iglesia, entre 1783 y 1823. Todos los retablos son de mármoles de colores, contando con la colaboración escultórica de Cosme Velázquez. El Marqués de Valde-Íñigo costeó el retablo mayor y participó en gran medida en todos los demás retablos para conseguir su terminación.
Erigida como parroquia en 1787 y situada en el centro histórico de la ciudad, la parroquia de Nuestra Señora del Rosario incluía, en el ámbito de su feligresía, a los principales órganos del comercio americano como fueron la Casa de la Contratación, el Tribunal del Consulado y la Aduana. Gracias a su privilegiada ubicación, esta parroquia se convirtió en un espacio donde se desarrolló la religiosidad de la burguesía mercantil gaditana, y en ella se crearon varias cofradías integradas mayoritariamente por miembros de este grupo social.
Para terminar este breve resumen de la historia de la parroquia, recordar que entre la extensa nómina de bautizados que se encuentran en sus libros sacramentales, destacan varios gaditanos que han tenido relevancia dentro de la política nacional como Mendizábal, Emilio Castelar o Segismundo Moret, o internacional como el general George G. Meade en Estados Unidos. En el campo de las artes y las letras, fueron bautizados en esta parroquia el músico Manuel de Falla y el escritor José María Pemán.