Каролингской часовни VIII века длительное время хватало для богослужебных нужд населения, пока Селеста оставалась небольшой деревней, где проживали в основном крестьяне, рыбаки и лодочники. В 1216 года поселение получило статус вольного города и было обнесено крепостной стеной. На следующий год император Фридрих II Штауфен заключил с приоратом Св. Фе соглашение, по которому жители частично освобождались от контроля со стороны этого бенедиктинского монастыря.
С тех пор население города стремительно увеличивалось. Гордые своей свободой и растущим благосостоянием, религиозные жители восприняли как одну из своих первоочередных задач строительство более просторной и более красивой церкви.
Работы по строительству новой церкви начались в 1220-х годах. Первоначально разработанный архитекторами план предусматривал возведение обширной базилики в романском стиле, состоящей из трех нефов и двух трансептов. На тот момент церковь была названа в честь Богоматери (Notre-Dame). Поскольку в богослужебных целях необходимо было как можно дольше сохранять древнюю ротонду, то сначала были возведены внешние стены боковых нефов. Со стороны южного бокового нефа от той эпохи сохранился прекрасный портал в переходном стиле, сочетающий в себе романские и раннеготические черты. Ок. 1230 года была построена алтарная часть с двумя апсидиолами, практически полностью перестроенная в XV веке. Центральный неф строился с 1235 года.
В 1240-1250 гг. каролингская ротонда была снесена, чтобы освободить место для строительства алтарной части и трансепта нового храма. Между тем на смену романскому стилю уже пришел готический. Ок. 1250 года, когда было начато строительство центрального нефа, эльзасское готическое искусство уже достигло расцвета (неф Кафедрального собора в Страсбурге был воздвигнут в 1250-1275 гг.). Не исключено, что планы строительства Страсбургского собора и церкви Св. Георгия в Селесте были разработаны одними и теми же архитекторами. В центральном нефе храма Селесты мы, хотя и в более простой форме, обнаруживаем то же строгое изящество, ту же чистоту линий и мистическое стремление ввысь, которые характерны для главного нефа собора в Страсбурге.
Приблизительно в 1300 году церковь была продолжена в западную сторону за счет постройки своего рода западного трансепта, который образует в интерьере храма некое подобие нартекса, вытянутой формы, охватывающего всю длину фасада. В центре фасада архитектор предусмотрел возведение башни, которая после ряда изменений в плане была построена в два этапа.