Postepeno jačanje Crkve Bosanske počinje od vremena vladavine bana Kulina (1180 – 1204). Takvo stanje nije pretjerano zanimalo susjednu Ugarsku koja je na njega više gledala politički nego vjerski. Dolaskom na vlast, ban Matej Ninoslav (1232 – 1249) nastoji da svoju poziciju ojača i u vjerskom i u političkom pogledu, poslije čega su se neki bosanski plemići oprli, oslanjajući se na hrvatskog hercega Kolomana, koji je tada vladao Hrvatskom i Slavonijom. Ninoslav se tada uputio papi na razgovor poslije čega je on 10. oktobra 1233. godine preporučio Kolomanu da pomogne Ninoslavu da ojača. Ovakav poziv shvaćen je totalno suprotno – da se Ninoslav nastoji odvojiti od ugarskog kraljevstva, pa je posegao za oružjem i poveo križarski pohod protiv Bosne. Da se ne bi ispostavilo da radi protiv pape, Koloman je nešto prije 14. oktobra 1234. godine papi Grguru IX javio da je “uzeo znak križa i odlučio krenuti na krivovjerce iz krajeva Slavonije koje će muževno iskorijeniti jakom rukom i snažnom desnicom”. Koloman je tada na Bosnu gledao kao na dio Slavonije. Vjerujući u Kolomanove iskrene namjere papa je 14. oktobra 1234. godine odobrio hercegov korak. Tri dana kasnije uputio je i pismo bosanskom biskupu Ivanu Nijemicu potičući ga da pomogne Kolomanu u “istrebljivanja krivovjerja iz Slavonije i njegove biskupije”.

Uvjeren da će pokoriti Bosnu, ugarski kralj Andrija II, pred svoju smrt, u februaru 1235. godine svom sinu Kolomanu daruje Bosnu. Križarska vojna otpočela je tek u proljeće 1235. godine. Sibislav, sin bivšeg bana Stjepana, i Prijezda se tada prikloniše Kolomanu smatrajući da je križarska vojna namijenjena isključivo protiv pripadnika Crkve bosanske. Ipak, sam ban Ninoslav se stavi na čelo države i povede vojsku protiv križara. Prema pismu pape Grgura IX od 9. avgusta 1235. godine Koloman je uspio zauzeti veći dio Bosne. U osvojenim krajevima spalio je na lomači veliki broj pripadnika Crkve bosanske koji nisu željeli napustiti svoju vjeru. Razočaran svirepošću Kolomana, bosanski biskup Ivan podnese ostavku na službi u Bosni. Pored svirepog ponašanja Kolomana biskup je u svom pismu papi naveo “da ga boli otpor napadnutih Bošnjana koji ne žele prihvatiti katoličanstvo”. U zimu 1235/36. godine herceg se sa križarima vratio kući. Ban Ninoslav se poslije ljetnih borbi 1235. godine povukao u nepristupačne krajeve jugoistočne Bosne i nastavio voditi otpor. Po svemu sudeći uspio je osloboditi veći dio Bosne jer se u Ugarskoj spremala nova vojska protiv Bosne. Za kneza župe Usore Koloman je postavio banovića Sibislava koji mu je vjerovatno pomogao prilikom borbi. Osim Sibislava na stranu Kolomana se stavio i ban Prijezda.

Nove borbe protiv Bošnjana su otpočele u proljeće 1237. godine. Dokaz tome imamo u odluci Dubrovnika od 18. maja gdje zabranjuju svojim građanima da trguju po Bosni zbog ratnog stanja. Bosanska vojska, predvođena banom Ninoslavom, se za novi križarski pohod daleko bolje spremila i pružila žestok otpor. Ipak, Koloman je na kraju ponovo zauzeo veći dio Bosne i Zahumlja do kraja 1237. godine. Tokom ljeta 1238. godine križari su držali veći dio zauzete zemlje, ali se ban Ninoslav sa bosanskom vojskom uspio održati u jednom dijelu zemlje – u teško pristupačnim planinskim dijelovima jugoistočne Bosne. Vidjevši nemogućnost da potpuno iskorijeni pripadnike Crkve bosanske i eliminiše bosansku vojsku, novi bosanski biskup Ponsa krajem jeseni 1238. godine se lično uputi papi u Rim kako bi od njega dobio odobrenje da on bude čelna figura u “istrebljenju protivnika katoličanstva i obnovi katoličke vjere”. Da bi se takav plan lakše ostvario papa 22. decembra 1238. godien izda 5 apostolskih pisama: prvo ostrogonskom nadbiskupu Robertu i njegovim podređenim biskupima da pomažu Ponsu pri istrebljenju krivovjeraca u Bosni; drugo hercegu Kolomanu potičući ga da “kako je negda, tako da i u buduće bude revan i postojan”, da bi tako dokazao “da si iz zemlje svoje odstranio sramotu krivovjeraca”; treće papino pismo upravljeno je pečuhskim dominikancima, da Ponsi predadnu novac, koji je njima negda predao ban Ninoslav za gradnju stolne crkve u Bosni; četvrto i peto pismo upravljeno je varadinskom benediktanskom opatu, kojemu papa nalaže, da Ponsi preda polog hrvatskog bana Jule i novac, što je sakupio i što će sakupiti za otkup križarskih zavjeta; šesto pismo upućeno je samom biskupu Ponsi u kojem ga papa imenuje svojim legatom u Bosni i daje mu posebne ovlasti na tri godine, da sakupi križare, koji bi se “muževno i snažno opasali, da ostatak krivojverne kuge iz bosanske biskupi odstrane”.

Koloman se održao u Bosni i Zahumlju od zime 1238. do kraja jeseni 1239. godine, kako je izvjestio papu Grgura IX. Papa mu u pismu od 5. decembra 1239. godine čestita na “ustrajanoj borbi protiv napadača na katoličku crkvu”. U jesen 1239. godine biskup Ponsa u Bosni podiže katedralnu crkvu i uz nju formirao katedralni zbor. Isti dan kada je papu izjestio o ovom činu, 7. decembra 1239. godine papa šalje pismo ugarskim dominikancima da “pošalju braću u Bosnu kako bi tamo učvrstili katoličku vjeru”. Kada je dobio vijest da su Tatari provalili u Rusiju Koloman se u zimu 1239/1240. godine povukao u Slavoniju, što je iskoristio ban Ninoslav da iz planinski dijelova jugoistočne Bosne krene u ofanzivu. Do kraja zime 1240. godine bosanska vojska je potpuno izbacila križare iz Bosne i oslobodila cijeli prostor zemlje. Da bi ponovo učvrstio svoje veze sa Dubrovnikom ban Ninoslav 29. marta 1240. godine odlazi u Dubrovnik gdje sklapa ugovor o “vječnom miru i prijateljstvu sa dubrovačkom republikom i njezinim knezom Nikolom Tinistom”.

Eliminacija križarskih četa koje je ostavio u Bosni je razbijesnila Kolomana. Ipak, on nije mogao poduzeti odlučujući korak jer se spremao za borbu protiv Tatara. U odlučujućoj bici na rijeci Šaju, u današnjoj Mađarskoj, u aprilu 1241. godine Koloman je doživio poraz te se ranjen povukao u utvrdu Čazme u Moslavini, gdje je preminuo. Tatarski pohod se poslije toga nije mogao spriječiti te su Tatari u konačnici prešli i preko same Bosne početkom 1242. godine. Tom prilikom su stradala brojna bosanska ravničarska mjesta kao i gradovi. Sam ban Ninoslav se sa narodom sakrio u planinskim krajevima do kojih Tatari nisu mogli doprijeti sa svojim konjima.