Fue fundado en 1295 por agustinas ermitañas en el emplazamiento conocido como "Degolladero de los Cristianos" o "Campo de los Mártires", que se localizaba a extramuros de la ciudad junto a la puerta de Córdoba. Su fundación fue auspiciada por el rey Fernando III, que llegó a acoger bajo el patrocinio de la corona en 1309.

El convento cambió de emplazamiento debido a los numerosos pillajes y asaltos que padeció, facilitados por la indefensión del cenobio dada su situación periférica. Fue el monarca Pedro I de Castilla quien dispuso por Real Licencia el traslado del convento intramuros.

El solar del primitivo convento se vendió en 1627 a los padres Capuchinos, que fundaron allí su convento dedicado a las Santas Justa y Rufina.

Las pequeñas dimensiones del nuevo establecimiento determinaron la marcha de la comunidad de religiosas en 1369. Esta se trasladó a la que se convertiría en su residencia definitiva, localizada en el espacio que ocuparon las casas de Teresa Jufre (de la familia de los Tenorios, mujer de Alvar Díaz de Mendoza), requisadas por el rey a la propietaria debido a su deslealtad. Ese mismo año se iniciaron las obras de adecuación y construcción del convento y su iglesia, que culminarían en 1377. Posteriormente la comunidad de religiosas agustinas comenzó a recibir múltiples mercedes donadas por la propia realeza, acumulando numerosos privilegios y riquezas, por los cuales el cenobio se vio sometido a importantes transformaciones desde entonces. Muestra de ello fue el levantamiento de una nueva iglesia en el siglo XVI, en cuya construcción intervinieron Asensio de Maeda (hacia 1584), Juan de Oviedo y los maestros albañiles Juan de los Reyes y Juan Miguel.

El siglo XIX fue difícil para el convento, debido a los generales motivos económicos, políticos y revolucionarios que le afectaron directamente (la invasión napoleónica, la desamortización de Mendizábal y la Revolución de 1868), aunque logró mantenerse con las pocas dotaciones que conseguía del arzobispado, continuando su funcionamiento en la actualidad.

En 1995 el cenobio de San Leandro de Sevilla fue declarado Bien de Interés Cultural con categoría de Monumento por Decreto de 29 de agosto de ese mismo año.

La iglesia del convento presenta una estructura de cajón y nave única, cubierta por una bóveda de cañón con lunetos, formando cuatro tramos entre arcos fajones. La portada de acceso al templo muestra un estilo manierista, mientras que el resto de portadas de entrada a las dependencias de clausura son de estilo clasicista con sobrias pilastras.

Los coros alto y bajo, a los pies de la iglesia, están cubiertos por una bóveda de cañón y decorados con yeserías del siglo XVI. Dentro de esta estancia destaca el retablo de la Virgen de la Granada, presidido por la imagen del mismo nombre, próxima al estilo de Jerónimo Hernández.

El claustro, igualmente datado en el siglo XVI, presenta una estructura romboidal, con doble galería de arcos peraltados en la planta baja y de medio punto en la superior, soportados por columnas de mármol.

Durante el siglo XVIII se reformaron el convento y la iglesia, dotando a la última de un retablo barroco que aún conserva actualmente. El Retablo Mayor, elaborado entre 1745 y 1748 por Pedro Duque Cornejo y Felipe Fernández del Castillo, muestra dos cuerpos, un ático y tres calles flanqueadas por estípites. En las calles laterales del primer cuerpo figuran las imágenes de las Santas Bárbara y Teresa (siglo XVIII) mientras que en la hornacina principal se inserta un Sagrado Corazón de Jesús moderno. El segundo cuerpo del retablo está presidido por una escultura de San Leandro del siglo XVIII, y en el ático aparece San Agustín ante Cristo y la Virgen. En las calles laterales de este segundo cuerpo y en las del ático se incluyen seis relieves, aprovechados del antiguo retablo de la iglesia (que realizó Jerónimo Hernández en 1583). Representan el Bautismo de Cristo, la Flagelación, la Adoración de los Reyes, la Asunción de la Virgen, la Oración del Huerto y a San Agustín.

En el interior del templo también se localizan otros dos retablos del siglo XVII, dedicados a los Santos Juan Bautista y Juan Evangelista, ambos elaborados por Martínez Montañés. El último de ellos también incorpora efigies de Santiago el Mayor, Santiago el Menor y un relieve con el Martirio de San Juan Evangelista, obras de Francisco de Ocampo.

Asimismo sobresalen otros relieves y retablos, entre los que cabe señalar uno dedicado a San Agustín, flanqueado por Santo Tomas de Villanueva y San Nicolás de Tolentino, datado en 1650 y elaborado por Francisco de Ribas; otro de estilo neoclásico de 1950, obra de José Mestre, dedicado a Santa Rita de Casia; y por último otro del último cuarto del siglo XVIII, que contiene una imagen de la Virgen María y el Niño Jesús de candelero (siglo XIX), y que se sitúa junto al cancel de la iglesia, de 1729.