Kako se sve dotadašnje ratovanje Mladena II. Šubića pretvorilo u stalne poraze, u Bosni su osjetili priliku da se konačno otarase bana. Osim tog, krstjani su se ponovo pobunili, a to se vidi iz pisma koje je pisao papa Mladenu. Ipak, prisjetio se da u Dubrovniku borave sinovi i supruga pokojnog bana Stjepana I. Kotromanića i dođe na ideju da ih iskoristi. Osim toga, mogao je sasvim jasno videti da krstjani upravo najstarijeg sina Stjepana I., koji se zvao također Stjepan (II.), priznaju za bana Bosne, smatrajući da po redu naslijeđa njemu pripada banska čast. Za Bošnjake Mladen II. Šubić nije bio ban kojeg bi oni priznavali i smatrali su ga uzurpatorom.

Od ženidbe sa Dragutinovom kćerkom potpao je ban Stjepan I pod njegov utjecaj i mnoge stvari koje je činio bile su plod Dragutinove volje. Nakon smrti ugarskog kralja Ladislava IV. 1290.  stvari su se promijenile. Pošto Ladislav IV. nije imao djece postavilo se pitanje nasljednika ugarske krune. Ipak, vrlo brzo nakon kraljeve smrti okrunjen je za novog kralja njegov rođak Andrija III. Mlečanin (1290.-1301.). Pošto je imao jaku opoziciju odmah su počele intrige. Kao najopasniji protivnik pojavio se napuljski kralj Karlo II (pripadnik Anžujske dinastije), muž Marije, inače sestre kralja pokojnog Ladislava IV. (1272.-1290.), koji je za svoga sina Karla Martela zatražio ugarski prijestol Arpadovića. Ova je stranka bila vrlo jaka pa je na kraju papa Nikola IV. okrunio Karla Martela (1290.-1295.) za ugarskog kralja. Uz ovu stranu tada su pristupili i najjači hrvatski velikaši, bribirski knezovi Šubići: Pavle I., Juraj II. i Mladen I. Kako je Dragutinova kćerka Urošica bila udata za Pavla I. Šubića sasvim je razumljivo da su Dragutin i njegov zet, ban Stjepan I. Kotromanić, pristupili odmah uz njih.

Dinastija Kotromanići

Najpoznatija legenda o porijeklu dinastije Kotromanić i o njihovom prezimenu je ona koju prezentira Mavro Orbini u svom djelu „Kraljevstvo Slavena“. Po njemu, nakon smrti Kulina bana, ugarski kralj, (Emerik ili Ladislav IV su vladali 1204. kad je umro Kulin ban), ali ne kaže se koji je kralj u pitanju Bosnu u je poslao jednog svog velikaša, porijeklom Nijemca, koji je imao zadatak zauzeti Bosnu. On se zvao Kotroman, a kako je bio vješt ratnik uspio je vrlo lako obaviti zadatak. Za nagradu, kralj ga je postavio bosanskim banom. Da je legenda uhvatila korjena vidi se iz nekih dubrovačkih pisama gdje se ban naziva „Cotromano Goto“. Danas se zna da Kotromanići nisu stranog, dakle ni gotskog ili germanskog porijekla i da potiču iz neke bosanske plemićke kuće, a da je ban Prijezda I osnivač ove dinastije. To djelimično potvrđuje i Mavro Orbini kad navodi da je: „njihova obitelj gotovo uvijek vladala u Bosni. Nekad su to bili banovi, a nekad kneževi“.

Bana Stjepana naslijedio je po svemu sudeći nasilno ban Matija Ninoslav. Njega su na bansku čast uzdigli krstjani, što je pomalo čudno budući da je u prvo vrijeme ban Ninoslav (dok nije postao ban) bio protivnik krstjana, vjeran ugarski vazal i gorljivi katolik. Spomenuti papa Grgur IX piše mu ljubazna pisma i obraća mu se sa „Grleći te iskrenom ljubavi, tvoju osobu i tvoju zemlju Bosnu primamo pod zaštitu sv. Petra i našu sa svim imanjima, koje sada pravedno držiš, i utvrđujemo te zaštitom ovoga pisma te strogo zabranjujemo, da se bilo tko usudi da te uznemirava, dok ostaneš u katoličkoj vjeri.“

Kulin ban je sa ženom Vojislavom imao sina Stjepana (1204.-1232.) koji ga je naslijedio na prijestolu Bosne, zapravo izabran je na Stanku Bosne (vlada) i bosanskom državnom Saboru od velikaša. Od početka vladanja ban Stjepan je imao dobre odnose s ugarskim dvorom i tamo je često boravio. U Bosni nije bio mnogo omiljen budući da je progonio krstjane, što govori da se na vlasti održavao isključivo zahvaljujući ugarskoj pomoći. Ban Stjepan je imao ženu Anku i sina Sebislava. Iz 1223. potiču prvi podaci o utjecaju Crkve bosanske na zapadne heretičke crkve u Italiji – katare i Francuskoj – albigenze.

Mada se 1180. godina uzima kao početak vladavine Kulina bana, visoki naslov kojim ga titulira legat (izaslanik) pape Inocenta III. (1179.-1180., on je zapravo protupapa) prilikom boravka u Bosni, govori da je ovaj vladar bio na čelu Bosne i prije te godine. Na stećku sudije Gradeše iz 1193. spominje se „veliki ban bosanski“ Kulin, a na natpisu iz Biskupića uz Kulina bana spominje se i njegova žena Vojislava. S obitelji velikog župana Stjepana Nemanje čak se i orodio budući da se Kulinova sestra udala za Nemanjinog brata Miroslava. Kulin ban, od ranije formalno vazal Ugarske, morao je kao nasljednik bana Borića dolaskom na prijestol Bosne preuzeti sve obaveze svog prethodnika, a onda kao saveznik, boriti se zajedno Ugrima i Srbima protiv bizantskog cara Andornika I Komnina (1183.-1185.)

Prvi po imenu poznati bosanski ban Borić spominje  se u vremenu od 1141.-1164. Ali neki povijesničari predpostavljaju da je i prije bana Borića Bosnom vladala domaća vladajuća dinastija. Kao obrazloženje toj hipotezi koriste se činjenicom da je bana Borića postavila prougarska struja bosanskih velikaša, jer je njegovo porijeklo iz Bosanske Posavine koja je naročito u to doba bila pod utjecajem Kraljevine Ugarske i jer se njegov dolazak na čelo banovine Bosne, po povijesnim izvorima odigrao s blagoslovom ugarskog kralja Bele II Slijepog (1131.-1141.) u zadnjoj godini njegove vladavine. Banovina Bosna je u to doba bila u vazalnom odnosu prema Kraljevini Ugarskoj, jer ugarski kralj Bela II od 1137.  u svojoj tituli navodi da je on ujedno i „kralj Rame“, a Rama je jedna od najstarijih župa srednjovjekovne Bosne i ujedno sinonim za tadašnju cijelu zemlju Bosnu.