W ok. 780 w Soest wzniesiono pierwszy kościół w miejscu obecnego kościoła św. Piotra w ramach polityki chrystianizacji Niemiec północnych prowadzonej przez Karola Wielkiego. Wraz z rozwojem miasta zrodziła się potrzeba zbudowania większej świątyni i nowy kościół został poświęcony w 1150 roku a dwa lata później kościół odwiedził cesarz Fryderyk I Barbarossa.
Soest było pod rządami arcybiskupów Kolonii, którzy w ok. 960-65 roku wznieśli koło kościoła św. Piotra palatium. W 962 roku arcybiskup Kolonii Bruno I sprowadził do Soest relikwie św. Patroclusa, a w 965 roku w swoim testamencie zapisał 100 funtów w srebrze na fundację świątyni, obecnej kolegiaty św. Patroclusa.
W połowie XII wieku Soest otrzymało prawa miejskie, które najprawdopodobniej wywodziły się z praw stosowanych w Lombardii. Prawa te miały wpływ na prawa miejskie nadane Kolonii oraz Lubece i były stosowane na obszarze od Nadrenii do Pogórza Wezerskiego oraz w Westfalii poza Dortmundem.