5 сентября 1910 г. можно считать днем рождения тартуского прихода Святого Павла. В этот день настоятелем городского отделения тартуского Мариинского прихода стал Арнольд Аугуст Виктор Хабихт. Устав прихода был утверждён 28 октября 1911 г. Название прихода – тартуский приход Святого Павла вступило в силу в конце января 1912 г. В пользование прихода была дана Мариинская церковь, где приход существовал до осени 1917 г. С созданием прихода родилась также и идея строительства церкви.
В январе 1911 г. Тартуская городская управа вынесла решение отдать участок, находящийся на улице Рийа, тартускому Свято-Павловскому приходу. Сразу же после того, как было найдено место для строительства, началось планирование церкви и поиски архитекторов. Прихожане ездили в Ригу осматривать только что построенную тогда церковь Святой Гертруды. Велись переговоры с архитектором Штюком (Franz von Styk). Обратились также к финскому архитектору Элиэлю Сааринену. Последний создал строительный план церкви и 21 декабря 1911 г. лично приехал в Тарту, чтобы ознакомить тартусцев с планом.
К созданию проекта церкви Элиэль Сааринен приступил в декабре 1911 года. Церковь была построена по проекту Сааринена 1913 года. По этому проекту здание состояло из трёх частей: в глубине участка располагалась церковь, и с нею соединялись два флигеля, расположенные вдоль улицы, между которыми находился открытый двор перед фасадом. Более или менее симметричное решение основной массы составляла средняя часть с церковным залом, значение и функция которой подчёркивалась башней.
Флигели соединялись с главным зданием через второй этаж. В правом флигеле планировалось разместить канцелярию и жилые помещения для приходских работников, в левом крыле – рабочие помещения прихода. Из двух флигелей церкви Святого Павла было построен лишь левый. Объединение разных зданий, связанных с церковной и приходской жизнью, в начале ХХ века было новым и необычным явлением в мире, первые церкви такого рода появились в Германии лишь в конце XIX века.
Главное здание церкви, идущее в направлении юго-запад – северо-запад, на генеральном плане имело традиционно симметричную композицию. К зданию, протяжённому горизонтально, прилегало довольно широкое здание с одним нефом, расположенное поперечно. Место для хора завершалось полукруглой выступающей апсидиальной задней частью алтаря. Таким образом, церковный зал представлял собой форму латинского креста, что, однако, из-за вспомогательных помещений, находящихся по обе стороны алтаря, с задней стороны оставалось незаметным.
Проект тартуской церкви Святого Павла был освящён 1 октября 1917 года.
Церковь Святого Павла была воздвигнута в эпоху войн и революций. В освященной церкви не было алтаря, колоколов, органа, она не была украшена и оштукатурена.
Альтарная часть приобрела новое оформление интерьера в 1923–1924 годах. Изменение его интерьера началось с приобретения в апсиду алтарной скульптуры. Амандус Адамсон (1855–1929) изваял алтарную скульптуру из каррарского мрамора в 1922 году в Италии. Скульптура “Приидите ко Мне все труждающиеся и обремененные” была освящена 17 марта 1923 года. Она изображала Иисуса Христа, под правой рукой которого находилась Мария Магдалина и под левой рукой – Иерихонский слепой, первая – как выразительница души, жаждушей избавления от душевных страданий и греховного бремени, и второй – как воплощение телесных мучений. Скульптура была выше человеческого роста – высотой 3,5 м без постамента.
В 1923 году архитектор Мильберг спроектировал новое оформление алтарного помещения, колорит которого был более тёмным. Работа была завершена в 1924 году. Однако, хотя окна были замурованы, по всей видимости, этого оказалось недостаточно, так как для того чтобы скульптура лучше выделялась, было проведено дополнительное электрическое освещение.
Колокола на церковной башне были освящены 13 декабря 1923 г. Они были отлиты в Бохуме, в Рурской области. Самый большой колокол (dis) “Я есмь глас вопиющего…” весил 1200 кг и самый маленький (fis) – “Направляет на стези правды ради имени Своего, и язык мой всякий день будет возвещать правду Твою” весил 800 кг. Центральное отопление было оборудовано в 1924 году, ниши для радиаторов которого были сооружены еще в 1917 году. В том же году был расширен также и орган, приобретённый в 1917 году.
Поскольку строительство обоих флигелей, казалось, не имело будущего, то в 1931 году помощник архитектора города Тарту Артур Кирсипу создал новый проект для постройки здания левого флигеля. Вместо рабочих помещений прихода, планировавшихся по проекту Сааринена, Кирсипу спроектировал на первом этаже канцелярию и другие служебные помещения, на втором этаже – квартиру настоятеля и на третьем этаже – квартиру помощника настоятеля. Флигель был передан приходу 4 ноября 1932 года.