El origen de esta iglesia es posible que fuera visigótico, pues existen varios relieves de esta época en su ábside, ejecutado ya en época mudéjar. Sea como fuere, las primeras citas documentales hablan de una escritura "sobre compra de varias posesiones a distintos personajes moros que habían quedado en Toledo después de ganada", que confirma que la zona norte de la ciudad era en época islámica un barrio en el que vivían personas de buen nivel que fueron vendiendo poco a poco sus viviendas a los nuevos pobladores cristianos castellanos. Este hecho, hace que historiadores como Sixto Ramón Parro indicasen que la Iglesia de San Vicente fue una de las primeras fundadas por Alfonso VI tras reconquistar la ciudad en 1085.
En el año 1125 ya es citada como parroquia, si bien desconocemos si era en referencia a este edificio, pues la parte más antigua que se conserva -el ábside- parece datarse a mediados del siglo XIII. Dicho ábside está un tanto modificado desde época barroca en que se colocó un escudo heráldico en piedra en su parte central.
Este ábside, también llamado "cubillo de San Vicente", presenta una notable altura, al parecer debida al rebajamiento del nivel de la calle Alfileritos que se hizo en siglos posteriores a su construcción. Ello provocó que la cimentación del mismo quedara a la vista, como hoy se observa, pudiendo apreciarse grandes sillares que algunos autores han querido intepretar como "opus africanum" (una técnica de aparejo utilizada en las arquitecturas clásicas tanto romana como cartaginesa, caracterizada por poseer sillares verticales, a modo de pilares, alternando con horizontales), si bien ello no está confirmado en este caso.
En época gótica, probablemente a finales del s. XIV, se reforzó el edificio y añadieron algunas capillas. Hacia 1598 se reformó bajo las trazas de Nicolás de Vergara el Mozo, en la época en la que se situaba justo al lado la Casa de la Inquisición. La cercanía de esta institución hizo que, a los pies de la iglesia se construyera la capilla del Espíritu Santo que contaba sobre ella con una tribuna "donde oyen misa los señores ynquisidores quando no quieren baxar a la yglesia", según narra el historiador Hurtado de Toledo. Esta capilla se derribó en 1795 cuando el cardenal Lorenzana compró la citada Casa de la Inquisición, edificando allí el Palacio Universitario.
A fines del XVI se reformó una de las capillas góticas, instalándose en ella la nueva capilla de la Asunción de Nuestra Señora, fundada por doña Isabel de Oballe (u Ovalle) en su testamento de 1557. Se ejecutó unos años después, entre 1597 y 1605 por Francisco de las Cuevas y Juan del Valle, decorándose con un fresco del genovés Alejandro Semino. Cuando este falleció, en ella se instaló por encargo el maravilloso retablo y lienzo del Greco en 1615.
En esa época se reforma la iglesia por su mal estado general, eliminándose la vieja torre mudéjar y ejecutándose en 1599 la nueva bajo la dirección de Lázaro Hernández, colaborador habitual de Nicolás de Vergara el Mozo, que la diseñó de manera original con planta de rombo en vez de cuadrada.
La parroquia fue suprimida en 1804, manteniendo el culto pero con un rango ya mucho menor. Las primeras fotos de su interior son estas imágenes tomadas por Casiano Alguacil y Baldomer Gili a comienzos del siglo XX cuando aún se usaba para fines de culto religioso.
El hecho de no ser ya cabeza de parroquia provocó que poco a poco su uso decayera mucho hasta que, en 1929, fue allí instalado un Museo de Arte con obras religiosas.
Tras cerrar el museo en 1961, en el edificio se hizo una gran reforma, que pasó a tener varios usos, como por ejemplo albergar clases y exámenes de la universidad regional.
En los primeros años del siglo XXI, la Iglesia de San Vicente fue restaurada íntegramente. Esta restauración es de las más originales, no ya de Toledo, sino probablemente de Europa pues se hizo para que pudiera albergar el Círculo de Arte donde hoy se celebran estupendos conciertos, exposiciones, presentaciones y noches de fiesta y jolgorio (eso sí que es un "Círculo vicioso"). Es una idea que a mí personalmente me encanta ya que era un edificio que se caía a pedazos (y lo digo literalmente pues recuerdo cómo me caían trozos del techo al papel en mis exámenes de selectividad allí efectuados en Junio de 1995) y la restauración ha sido muy respetuosoa con el edificio original. En cuanto a su uso, pues indudablemente ha mejorado mucho la vida cultural de la ciudad sobre todo en lo musical y es una de las mejores salas de conciertos actualmente en España.
En la plaza que lleva el nombre de la iglesia, en los últimos años, varios emblemáticos edificios que la dan forma han sufrido restauraciones, arreglos y reparaciones de lo más variopinto. Hace pocos meses empezaron las obras de reparación del Convento de las Gaitanas, hace años se remodeló la actual sede de la Cámara de Comercio, el Palacio Universitario Lorenzana está permanentemente siendo remodelado.
Esta es una reseña de 1929 con motivo de la apertura del museo:
