Сент-Пол тарихы еуропалықтар келгенге дейін ертеден басталады, ол кезде бұл жерлерді өздерінен кейін қорғандар қалдырған үндіс тайпалары мекендеген, оларды бүгін де қала маңынан табуға болады. Алғашқы еуропалық қоныс мұнда 1838 жылы пайда болды. Бастапқыда ол өзінің негізін қалаушы, эксцентрлі саудагер және бутлегер Пьер Парранттың құрметіне «Шошқа көзі» (Pig's Eye) деген бейресми атаумен белгілі болды. Алайда 1841 жылы католик миссионері Люсьен Гальтье өзен жағасында бөренеден шіркеу салып, оны апостол Павелдің құрметіне бағыштады. Көп ұзамай бұл атау, Сент-Пол, бүкіл қонысқа берілді.
Қаланың дамуы бірнеше негізгі факторлармен тығыз байланысты болды. Біріншіден, оның Миссисипи өзеніндегі, 1819 жылы салынған американдық әскери Форт Снеллингке жақын стратегиялық орналасуы. Форт қауіпсіздікті қамтамасыз етіп, қоныстанушыларды тартты, ал өзен басты көлік артериясы қызметін атқарды. Екіншіден, 1849 жылы Сент-Пол жаңадан құрылған Миннесота территориясының астанасы болып таңдалды, бұл оған бірден саяси салмақ берді. 1858 жылы Миннесота штат болған кезде, Сент-Пол өзінің астаналық мәртебесін сақтап қалды. Сонымен қатар, XIX ғасырдың екінші жартысында қала ірі теміржол торабына айналды, бұл оның Орта Батыстағы маңызды сауда және тарату орталығы ретіндегі рөлін нығайтты.
Ең басынан-ақ Сент-Пол мәдениеттер тоғысқан орта болды. Алғашқы қоныстанушылар негізінен франко-канадалық тері саудагерлері, сондай-ақ ирландық және неміс иммигранттары болды. Бұл мәдени әртүрлілік қаланың архитектурасы мен дәстүрлерінде көрініс тапты. Ертеректегі Сент-Пол экономикасы тері саудасына сүйенді, ал өзен портының арқасында қала батысқа бет алған қоныстанушылар үшін маңызды ауыстырып тиеу пунктіне айналды. XX ғасырдың басына қарай мұнда машина жасау, тамақ және ағаш өңдеу өнеркәсібі белсенді дамып, Сент-Полді аймақтың маңызды өнеркәсіптік және қаржылық орталығына айналдырды.