La llegada de los agustinos a la ciudad de Valencia se materializa en torno al año 1258, pero no será hasta el año 1307 cuando levanten su convento. Los agustinos levantaron el convento primitivo, extramuros de la ciudad, junto al conocido como Camino de San Vicente que llevaba al Convento de la Roqueta. La fundación corrió a cargo de fray Francisco Salelles (fallecido en 1310) (frater Franciscus de Salelles). Su sepulcro en piedra se encontraba en el monasterio, hasta que en 1835 al ser desamortizado, pasó a propiedad del Museo del Carmen (antecesor del Museo de Bellas Artes de Valencia). Con la construcción en 1356 de la nueva muralla cristiana el antiguo convento quedó intramuros de la ciudad pegado a la muralla y muy cercano de la Puerta de San Vicente.

Llama la atención en el plano del padre Tosca fechado en 1704 que junto al convento se levantaba una cruz. Según se dice esta cruz fue levantada como recuerdo que en aquel lugar se encontraba el cementerio parroquial de la iglesia de San Andrés que fue derribado en 1640 al abrirse la nueva plaza.

Para comprender la importancia de este monasterio diremos que disponía de refectorio, enfermeria, noviciado, celdas para los monjes, dos claustros, porteria y que su biblioteca situada en el piso superior del refectorio albergaba mas de 120.000 volumenes. En su época de mayor esplendor ocupaba una superficie que iba desde su actual emplazamiento hasta cerca de donde se encuentra hoy en día el MUVIM, en los jardines del antiguo Hospital General.

Después del paso de los franceses durante la guerra de la independencia el convento quedó, practicamente arruinado. El convento había sido convertido en Cuartel militar y todas las obras de arte que no pudieron ser salvadas antes de la toma de la ciudad, desaparecieron, incluida la biblioteca de la que no quedaron ni los estantes. En 1815 los agustinos pudieron volver al monasterio una vez abandonado por los franceses pero a partir de ese momento el convento no pudo reponerse de las perdidas sufridas.

El 6 de agosto de 1835 el convento sería abandonado por los religiosos como consecuencia del decreto de desamortización de Mendizabal. La iglesia continuaría cumpliendo exclusivamente función de parroquia a petición de los vecinos. Esta se volvería a reabrir el 1 de noviembre de 1836.

El convento disponía de un clautro gótico situado en el lugar que ahora ocupan los jardines junto a la iglesia. En 1622 (siglo XVII) Juan Jerónimo de Ranyaga (Joan Geroni de Ranyaga) construye un nuevo claustro de dos pisos, y además un segundo piso en el viejo gótico. Ambos claustros quedaban separados por un cuerpo en cuya planta baja se encontraba el refectorio y en la parte superior la biblioteca. Por descripciones sabemos que eran grandes y que el claustro moderno era aún mayor que el gótico, pues disponía de 28 arcadas, tenía las paredes chapadas con azulejos y en las columnas se disponían imagenes de santos y eclesiásticos. El primer piso se sustentaba sobre columnas de orden dórico, mientras que el segundo piso se disponía mediante columnas jónicas. El viejo claustro gótico lo formaban arcos apuntados y se cubria con bóvedas de crucería. Disponía de dieciseis arcadas por panda lo que nos puede dar idea de su tamaño y establecer comparación con el nuevo. Hoy en día, lo único que queda de los claustros es el muro medianero que unía la iglesia y el claustro viejo.

En 1902 se trasladó a esta iglesia la antigua parroquia de Santa Catalina martir, llamándose desde entonces de Santa Catalina Mártir y San Agustin, aunque lo que es el convento fue demolido en 1904, quedando sólo en pie la iglesia.

En 1936 el templo fue destruido durante la Guerra Civil y a partir de 1945 es repristinado conservando el nombre de Iglesia de San Agustin. Las obras de restauración corrieron a cargo del arquitecto mayor del Ayuntamiento de Valencia Javier Goerlich Lleó. Entre las intervenciones mas criticables de este arquitecto tal vez sean, la apertura de una nueva portada que nunca tuvo recayente a la calle Játiva y la construcción de la torre que ahora dispone, ambos elementos un tanto extraños a las caracteristicas originales del templo.

El campanario por referencias que disponemos sabemos que estaba situado en el lado contrario a donde se encuentra en estos momentos, que era de planta cuadrada y el mismo estaba almenado. Fue realizado por Juan Bautista Perez Castiel. También fue obra de Perez Castiel la Sala Capitular hoy desaparecida.

En 1912 el arquitecto Luis Ferreres Soler (1852-1926) levanta un nuevo campanario, en estilo ecléctico con reminiscencias góticas en su actual emplazamiento, que es el que se conserva actualmente, aunque reformado y modificado como hemos comentado bien entrado el siglo XX por Javier Goerlich.

La entrada al convento se realizaba por su fachada principal que estaba situada en la actual calle Huesca y que entoncés era conocida como Porteria de San Agustín. Sin embargo la entrada al templo desde la calle se hacia por la fachada sur de la iglesia hoy plaza de San Agustin.

La entrada al templo se realiza por la portada recayente a la plaza de San Agustin, es la habitual de entrada al templo. De estilo barroco se fecha en el primer tercio del siglo XVII y se compone de una puerta adintelada, flanqueada por dos pares de columnas estriadas en la parte media superior que apean sobre basamentos. En el cuerpo superior un frontón curvo partido, en cuyo centro y en el interior de una hornacina se dispone una imagen del santo titular de la iglesia (San Agustin), realizada después de 1936 por José Justo Villalba. Por encima del santo en un frontón partido figura el escudo de los agustinos: un corazón traspasado por una flecha. La portada permite el acceso a la iglesia por el lado de la epistola.

La iglesia se corresponde con un planteamiento gótico francés, donde la sobriedad de la decoración es patente, enfatizado si cabe además por el hecho de tratarse de un templo de origen conventual y no dedicado a la feligresía.

Es un templo fechado en el siglo XIV de una sola nave sin crucero, dividida en siete tramos cubiertos con bóvedas de crucería simple. Los nervios apoyan sobre mensulas directamente en el muro. Capillas entre los contrafuertes cubiertas a su vez por bóvedas sobre ojivas que también apoyan en mensulas. Coro elevado sobre arcos rebajados a los pies, donde además se encuentra el órgano. El último tramo más cercano a los pies queda separada por una verja metalica, lo que le da aspecto de atrio cubierto. El primer tramo de la bóveda de crucería de la nave central es más ancha que las restantes ya que cubre el espacio de dos de las capillas laterales. La cabecera se compone de un ábside poligonal de cinco lados cubierta con bóveda de crucería estrellada con terceletes. En la clave central de esta bóveda encontramos una talla de la Virgen de Gracia con el Niño.

Los nervios de la bóveda presbiterial apoyan en columnillas con capiteles decorados. En cuatro de ellos encontramos a los cuatro evangelistas (tetramorfos), y en las dos restantes a San Miguel luchando con el demonio y al arcángel San Rafael con Tobias.

En 1692 fray José Milán Aragón prior del convento, encargó la renovación y recubrimiento interior del templo, con yesos y caracteres barrocos propios de la época, posteriormente en el siglo XIX volvería a ser renovada con elementos neoclásicos. En la restauración del templo de 1940 seran eliminados todos estos elementos ajenos al gótico original de la iglesia.

No obstante la pieza mas sobresaliente que dispone la iglesia sea una imagen o icono de estilo bizantino, conocida como "Mare de Deu de Gracia" (Nuestra Señora de Gracia), de gran devoción en su época, hasta el punto que en las cercanias de la iglesia una calle lleva el nombre de esta imagen sagrada. Se considera que dada la escasa tradición habida en España en esta clase de imagenes, el icono tenga su origen en Italia.

Este icono se considera de finales del siglo XIII o principios del XIV. Realizada al temple sobre tabla, representa a la Virgen vestida a la usanza oriental (con un maphorion o velo), sujetando al Niño con su brazo izquierdo y la mano derecha apoyada en la rodilla del Niño. Este sujeta con un cordel la pata de un pajarillo. El nombre de Nuestra Señora de Gracia le viene porque según cuenta la tradición: hacia 1307 una vez levantado el monasterio, dos monjes agustinos salieron del cenobio con la intención de encargar una imagen de Nuestra Señora a algún artesano de la ciudad. En el camino se encontraron con un extranjero vestido de peregrino que les preguntó por su misión. Los monjes le explicaron que habian salido del monasterio con el encargo de comprar una imagen de Nuestra Señora, acto seguido el peregrino les entregó un icono de la virgen y les dijo: "DA VOBIS DE GRATIA" (Os la doy de Gracia), es decir gratis. Posteriormente la figura del peregrino se convertiría en un ángel por la piedad de los fieles.

La primera capilla de la Virgen de Gracia se encontraba en el clautro gótico, fue realizada en 1370 y fue sufragada por el rey de Castilla Enrique II Trastámara (1369-1379) que la puso bajo su real patronato y protección. En 1692 la vieja capilla de la Virgen de Gracia sería renovada al igual que el templo. Entre 1750 y 1754 se construye una nueva capilla bajo el patronato del rey Fernando VI con planta de cruz griega y cubierta con cúpula. El retablo de la capilla era obra de Francisco Vergara el Mayor y a la muerte de este continuada por su hijo Ignacio Vergara. La pintura de la bóveda era a su vez obra de José Vergara. Esta capilla se situaba en el lado del evangelio cerca de la cabecera. Era de grandes dimensiones ya que sobresalía en planta sobre el clautro gótico.

En 1835 con la exclaustración, la capilla fue destruida pero milagrosamente la tabla se salvó al ser llevada al Convento agustino de monjas de la Presentación que se levantaba en el lugar que hoy ocupa el edificio del Instituto Nacional de Previsión (en la calle Marqués de Sotelo, cerca del Ayuntameinto). En 1836 al ser reabierta la iglesia la Cofradía de Nuestra Señora de Gracia devolvió el icono al templo siendo colocada en la primera capilla por el lado de la epistola, capilla que sería derribada en 1906 al urbanizar la nueva plaza de San Agustin, ya que los muros de la capilla sobresalian en exceso al exterior de la calle.

Después de la Guerra Civil (1936-1939) la tabla que habia sido escondida en casa de un feligrés, fue colocada en el Altar Mayor en un retablo de piedra neogótico realizado en alabastro por José Justo Villalba. El retablo se compone de dos cuerpos, el inferior adopta distribución horizontal y en su frontal podemos ver dos altorrelieves con escenas de la vida de Jesús: Jesús y la Samaritana y La cena de Emaús. En los extremos de de este cuerpo dos esculturas de bulto redondo representando a San Agustín y a Santa Catalina de Alejandria titulares del templo. El segundo cuerpo, de distribución vertical, adopta la forma de una portada de inspiración gótica flanqueada por dos pináculos góticos reinterpretados. En el centro del retablo una hornacina con el icono de la Virgen de Gracia y en las jambas que formarían esta supuesta portada doce pequeñas esculturas de los doce apóstoles. Las enjutas que forma el arco apuntado se decoran con altorrelieves con el sacrificio de Isaac. El retablo se levanta sobre un alto basamento o zócalo.

Como dato anecdótico podemos citar que el escultor Ignacio Vergara fue enterrado en este convento en 1776 ya que era miembro de la Cofradia de Nuestra Señora de la Consolación y Correa que tenía su capilla fundacional en el convento y de la que era muy devoto.

La iglesia dispone de seis capillas laterales entre los contrafuertes:

lado del evangelio comenzando por la cabecera
- Puerta de acceso al edificio de la Casa de la Enseñanza (de la Parroquia de San Agustín)
- Cristo Crucificado (de la preciosa sangre y providencia)
- Santa Rita de Cascia
- San Vicente Ferrer
- Santa Marta
- Sagrado Corazón de Jesús

lado de la espistola comenzando por la cabecera
- Retablo
- San José
- Virgen de los Desamparados
- Virgen Inmaculada
- Ocupada por la puerta lateral de entrada y salida del templo
- San Blas

En 1835 los monjes habian abandonado el monasterio y en 1836 la iglesia cumplía funciones de parroquial. En 1838 el coronel Manuel Montesinos Molina (1793-1862) a cargo de los presos de las Torres de Quart, solicita a las autoridades civiles la propiedad del convento para albergar a los presos que se encontraban en las torres ya que estas no reunian las condiciones higienicas y de seguridad necesarias. Le fue concedido el permiso para trasladarlos y el convento de San Agustin se convirtió en prisión y correccional. La primera medida que tomó Manuel Montesinos fue derribar la capilla de la Virgen de Gracia que ocupaba parte del claustro gótico y que molestaba para las nuevas funciones de prisión.

El convento albergó la prisión hasta 1893 en que fue abandonado por los últimos presos. Ya en 1841 los primeros presos lo habian abandonado con destino al nuevo correccional de San Miguel de los Reyes. El motivo de dicho abandono fue las constantes quejas de los vecinos que no querian un correccional en el centro de la ciudad cerca de sus casas. Se decidió que con la venta de los terrenos del convento se sufragaria la construcción de una nueva cárcel (La Cárcel Modelo). El convento fue demolido en 1903 y con el importe de la venta no se sufragó la construcción de la nueva cárcel. Sobre los terrenos que ocupaba el convento en 1925 se instaló el primer Mercado de Abastos que dispuso Valencia, después de la Guerra Civil se levantaria en su lugar el edificio de Hacienda que todavia podemos ver.