Los jesuitas llegaron a Palencia en julio de 1559, gracias al apoyo de Don Suero Vega, hijo de del Virrey de Sicilia Don Juan de Vega, que solicitó al Padre Laínez la fundación de un colegio de la Compañía en la ciudad castellana. Los primeros religiosos enviados fueron los padres Saavedra y Ayala, que junto a otros dos jesuitas se instalaron en una casa de la calle Mayor para predicar e impartir catequesis.

El asentamiento definitivo del colegio y de la iglesia se llevó a cabo en un solar muy cerca de un convento de franciscanos, lo que trajo consigo el recelo de estos religiosos por la proximidad con la nueva casa jesuita.

El primer rector del centro fue el padre Hernando Álvarez de Águila y en él se impartieron enseñanzas de gramática, de primeras letras y de filosofía para los propios jesuitas. Además de la labor educativa, la comunidad de Palencia destacó por las misiones populares en pueblos cercanos y la organización de una cofradía dedicada a la caridad y a la atención de los más necesitados, pobres y enfermos.

El templo fue construido entre 1584 y 1599, bajo la advocación de San Lorenzo. Inaugurado con una ceremonia presidida por el deán Don Francisco Reynoso, seguía el modelo de la casa madre de Roma creado por Vignola, con una cubierta de bóveda de cañón y una sola nave de tres tramos, el primero destinado al coro y los otros dos abiertos a capillas laterales comunicadas.

Tras la expulsión de la Orden de España en 1767, el edificio quedó convertido en parroquia-santuario al colocarse en su interior la imagen de la Virgen de la Calle, que desde entonces le da nombre, aunque también se le sigue conociendo como iglesia de la Compañía. En 1982 recibió la calificación de Bien de Interés Cultural con categoría de Monumento Histórico-Artístico de interés nacional. En 1871 los jesuitas volvieron a Palencia estableciéndose en la iglesia del exclaustrado convento de San Francisco.