Este monasterio se habría fundado alrededor del año 1200, en la misma época que la villa de Sarria, en pleno Camino de Santiago. Tradicionalmente se ha dicho que dos italianos, de regreso de su peregrinación a Santiago decidieron fundar un monasterio y hospital para atender a los peregrinos, donde ya existía una capilla dedicada a san Blas. Según Marcos Quesada (prior del convento, en 1666) el establecimiento fue fundado en el siglo XIII por religiosos de la «Congregación de la Penitencia de los Mártires de Cristo» venidos de Italia. La primera noticia documentada de este monasterio y hospital es del 1219, y se menciona su comendador.

Aquellos primeros ocupantes del monasterio se denominaban «Laudantes Deum» y se piensa que podría tratarse de una de las múltiples variantes de los «ermitaños de San Agustín», seguidores de la regla así conocida. En un documento firmado en 1251 su superior sometió el monasterio al obispo de Lugo y estableció que si los «hermanos de la orden de los Laudantes Deum» dejaran la casa, deberían devolverla a la Iglesia de Lugo. En 1332 fue emitida una bula por el papa Juan XXIII a favor del «Convento de la Magdalena de los Padres de la Penitencia de los Bienaventurados Mártires de Cristo, Orden de San Agustín de Sarria» otorgando unas indulgencias. Se trataría de una orden autónoma, cuyos miembros no eran conocidos como agustinos sino como «magdalenos». Constan dos prioratos dependientes de aquí.

En 1534 el papa Clemente VII nombró fray Álvaro Pérez de Sarria prior vitalicio del monasterio, el cual acumuló mucho poder hasta que en época del Concilio de Trento fue destituido por la fuerza. En 1568, con la intervención de gente armada, se obligó a la comunidad a ponerse bajo la observancia del la orden de San Agustín. Álvaro Pérez aceptó someterse a esta obediencia pero no quiso renunciar al cargo de prior que le había otorgado el papa. El resultado fue la incautación de la casa y la expulsión inmediata de la comunidad, sacándola físicamente del convento. Después abrieron de nuevo las puertas y los frailes regresaron, haciendo una declaración de sus bienes de los cuales fueron desposeídos. El más afectado fue el prior que había acumulado una importante fortuna.