L’origen d’aquest monestir cal cercar-lo en un establiment anterior que s’aixecava a llevant d’aquest lloc, conegut com San Andrés de Valbení i documentat des del 1093. L’any 1165 el lloc de San Andrés fou donat per Alfons VIII a Diego Martínez amb la finalitat de restaurar-lo monàsticament ja que en aquell moment es trobava en estat d’abandó, aquest personatge el va lliurar el mateix any a Santa María de Valbuena que hi va instaurar una casa depenent fins que el 1175 Alfons VIII ratificava les seves possessions com abadia cistercenca independent. El 1213 Alfonso Téllez de Meneses va fer donació a l’abadia de San Andrés del lloc de Palazuelos amb la condició que hi traslladés la comunitat, fet que es realitzà l’any 1226, mantenint el lloc de San Andrés com a granja de Palazuelos.

La nova casa monàstica de Palazuelos, es va convertir, a més, en panteó familiar dels Meneses. Era en aquesta època un centre monàstic ric però amb els anys va anar perdent els seus béns i al segle XVI es trobava en plena decadència. El 1835 la precària comunitat fou exclaustrada i el 1841 es va procedir a la seva subhasta. A partir d’aquí les construccions van anar patint el pas del temps i l’abandonament, el monestir es va perdre i ara (2010) només en resta l’església, propietat del bisbat, molt mal conservada i en perill de ruïna.