When the church of Patersberg was built, and who constructed it, is completely unknown.
It is said to have been a pilgrimage church in the early Middle Ages. It is certain that the church was originally dedicated to Saint Pancras. The church likely developed in three construction phases. The tower is early Gothic, still revealing Romanesque spatial perceptions and may have been built in its current form around 1200. Three Romanesque columns at the upper church tower windows remain a mystery; they are surely older. The rest of the church is Romanesque. The nave is estimated to date back to the 12th century, while the choir may have been built as early as 1100 or even 900. Perhaps the church also served defensive purposes at one time. The tower still shows several arrow slits today. The nave used to have more small windows (or at least niches) than it does today. The lower level of the tower is covered by a ribbed vault.