La historia del priorato de Nuestra Señora del Puente está inextricablemente relacionada con aquella del puente de Deustamben, asociado con el arquitecto leonés "Petrus Deustamben" (Pedro de Dios).

El primer testimonio conocido en el que encontramos referencia tanto del puente como del priorato data del año 1140. Se habla de un puente denominado"Deus", situado sobre el río Esla, junto al cual se encontraban numerosas propiedades pertenecientes al don Jimeno obispo de Astorga; los lugares citados son Arcos y Milles de la Polvorosa.

Según el testamento de Gutierre Muñoz del año 1196, poseedor de los bienes de Arcos de la Polvorosa, la heredad del Puente de Deustamben se componía del propio puente, de una iglesia dedicada a Santa María, a un hospital, y otras múltiples pertenencias. Probablemente este conjunto era el resultado de una participación comunal de los varios herederos de Muñoz.

De todas formas estos bienes, a través de una donación, pasaron a formar parte del dominio del monasterio de Benevívere situado en Carrión de los Condes. Este monasterio, desde siempre encomendado a los canónigos regulares de San Agustín, además sede de la Orden de Santa María de Benevívere, aparte de disponer de una extensa red de propiedades, también contaba con seis prioratos: Santiago de la Tola, en Ceinos de Campos (Valladolid); San Salvador de Villarmiel (Palencia); San Martín de Pereda, en la comarca de Riaño (León); Nuestra Señora de Mañino, en Sotobañado (Palencia); San Torcuato, junto al monasterio de Benevívire y, finalmente, Santa María de la Puente, en el Puente de Deustamben.

Según la heredad de Gutierre Muñoz, se establece que esta de Santa María de la Puente sea siempre abadía filial del monasterio de Benevívere y que tenga que admitir a todos aquellos familiares de los fundadores con la voluntad de querer ingresar al cenobio, incluso mujeres, aunque era este un monasterio masculino.

Pocas o ningunas son las noticias referidas al priorato durante el siglo XIII, y todas de manera de indirecta.

En el siglo XIV sabemos que el puente de Deustamben ha dejado de utilizarse. Aquí se pierden las noticias sobre este lugar.

En el Diccionario de Miñano encontramos una entrada con referencia al Priorato del Puente:"Lugar eclesiástico de España, provincia de Valladolid. A. P., 2 vecinos, no habitado. Situado a la inmediación de los ríos Castrogonzalo (sic) y Órbigo, reunidos a un cuarto de legua del Esla. Confina con los pueblos de Arcos y Milles de la Polvorosas, y con Villabeza del agua. Este priorato es exento con su término redondo, y constaba de parroquia y jurisdicción ordinaria del ilustre abad de Benevívere, que tiene la prorrogativa de conferir todos los prioratos y administraciones como los antiguos abades perpetuos. Se celebra en él un mercado todos los lunes del año. Produce lino y centeno. Dista media luega N. de la Puebla".

Respecto a nuestro puente, el corresponsal de Madoz, a mediados del siglo XIX, ya se ocupa con cierta amplitud al hablar de Arcos de la Polvorosa y el río Esla dice: "Se descubren cimientos de un puente de piedra que demuestran haber sido magnífico; comprende los despoblados de Subcastro, Cejinas y Velilla; el caserío y coto redondo del priorato de Nuestra Señora del Puente, cuyo convento de religiosos, anterior a la existencia del pueblo, está destruido".