Vokalisti Paul Janeway ja basisti Jesse Phillips tapasivat toisensa 2000-luvun puolivälissä, kun he soittivat Birminghamissa osana vaihtoehtoista soul-yhtyettä The Secret Dangers. Vuonna 2012 Jesse ja Paul tapasivat jälleen Ol’ Elegante Studiosissa Birminghamissa aloittaakseen uuden projektin. Janeway sanoo Phillipsin kanssa tehdystä projektista: ”Sen piti olla viimeinen hurraamme” ennen kuin keskittyisimme muihin uriin, ”mutta sitten jokin vain napsahti kohdalleen, ja kävelimme sieltä ulos jonkin kanssa”. Kun nämä kaksi alkoivat työskennellä Janewayn äänen ympärillä, he tajusivat muodostavansa soul-yhtyeen. Projektin edetessä pari otti mukaan Browan Lollarin, entisen The 400 Unitin, Andrew Leen, Ben Grinerin ja Allen Branstetterin. Täällä he nauhoittivat ensimmäisen EP:nsä, Greetings from St. Paul and The Broken Bonesin, ennen kuin he olivat koskaan soittaneet livekeikkaa.
Vapautettuaan Greetings from St. Paul and The Broken Bonesin bändi sai huomiota niin managerien kuin levy-yhtiöidenkin taholta. Tammikuussa 2013 yhtye aloitti ensimmäisen täyspitkän albuminsa Half the City äänitykset Nutthouse Recording Studios Sheffieldissä, Alabamassa ja Fame Studiosissa Muscle Shoalsissa, Alabamassa. Levyä äänittäessään bändi otti mukaan Al Gamblen soittamaan koskettimia. Gamble jatkoi soittamista St. Paul and The Broken Bonesin kanssa ja on ollut täyspäiväinen jäsen tammikuusta 2014 lähtien. Half the Cityn tuotti Alabama Shakesin Ben Tanner.
Helmikuussa 2013 St. Paul and The Broken Bones sai Thirty Tigers -yhtyeen Traci Thomasin huomion, joka pestautui heidän managerikseen. Pian tämän jälkeen he aloittivat viikonloppukiertueet Greetings from St. Paul and The Broken Bones EP:llä, odottaen torvensoittajien valmistumista yliopistosta ennen laajempien kiertueiden aloittamista.
Helmikuun 18. päivänä 2014 LP julkaistiin Single Lock Recordsin alla, joka on Florencessa, Alabamassa sijaitseva levy-yhtiö, jonka omistavat Ben Tannerin, Will Trappin ja The Civil Warsin John Paul White. Välittömästi Half the City sai kriittistä suosiota monilta kansallisilta toimittajilta, kuten Paste-lehdeltä, Garden and Gunilta, Southern Livingiltä, Rolling Stonelta ja NPR:ltä. Ensimmäisellä myyntiviikollaan Half the City nousi Billboard 200 -listalla sijalle 62. NPR:n Morning Editionin merkittävien juttujen ja CBS:n This Morning -televisiodebyytin jälkeen: Saturday, St. Paul and The Broken Bonesin debyyttialbumi nousi Billboard 200 -listalla sijalle 56. Oman kiertueensa lisäksi yhtye avasi The Rolling Stonesin Zip Code Tour -kiertueen Atlantassa, Georgiassa 9. kesäkuuta 2015 ja Buffalossa, New Yorkissa 11. heinäkuuta 2015. He esittivät kappaleen ”All I Ever Wonder” livenä BBC2:lla Glastonbury-festivaaleilta 25. kesäkuuta 2016.
Toukokuussa 2015 pasunisti Ben Griner jätti yhtyeen työskennelläkseen henkilökohtaisten projektien parissa.
Heidän toinen albuminsa Sea of Noise julkaistiin syyskuussa 2016.
Yhtye julkaisi singlen ”Apollo” kesäkuussa 2018 ja ilmoitti syyskuussa julkaistavasta albumista Young Sick Camellia.
Paul Janeway oli mukana Sigalan vuoden 2018 albumin Brighter Days nimikkoleikkauksessa.
Pul Janeway oli mukana Sigalan vuoden 2018 albumin Brighter Days nimikkoleikkauksessa.