El origen de este monasterio hay que buscarlo en un establecimiento anterior que se levantaba a levante de este sitio, conocido como San Andrés de Valbení y documentado desde 1093. En 1165 el lugar de San Andrés fue entregado por Alfonso VIII a Diego Martínez con el fin de restaurarlo monásticamente ya que en aquel momento se encontraba en estado de abandono, este personaje lo entregó el mismo año a Santa María de Valbuena que instauró una casa dependiente hasta que en 1175 Alfonso VIII ratificaba sus posesiones como abadía cisterciense independiente. En 1213 Alfonso Téllez de Meneses hizo donación a la abadía de San Andrés del lugar de Palazuelos con la condición de que trasladara allí la comunidad, cosa que se realizó en 1226, manteniendo el lugar de San Andrés como granja de Palazuelos.

La nueva casa monástica de Palazuelos, se convirtió, además, en panteón familiar de los Meneses. Era en esta época un centro monástico rico pero con los años fue perdiendo sus bienes y en el siglo XVI se encontraba en plena decadencia. En 1835 la precaria comunidad fue exclaustrada y en 1841 se procedió a su subasta. A partir de aquí las construcciones fueron sufriendo el paso del tiempo y el abandono, el monasterio se perdió y ahora (2010) sólo queda la iglesia, propiedad del obispado, muy mal conservada y en peligro de ruina.