U ovo vreme beše naročito ozloglašena na papskoj kuriji bosanska država. Dostave, da se tamo uvrežila neka opasna jeres, gonile su na aktivnost i Rim i Budim; prvi iz verskih, a drugi iz političkih motiva. Primer jake ruke, koja je u božjem gnevu "divno besnela" strahovitim ocenama u Tuluzi, u Francuskoj, izgledao je kao stvoren i za poluvarvarsku Bosnu. Šaljući 1221. god. svog legata Akoncija u Bosnu, papa se tužio da jeretici tamo javno ispovedaju svoju veru "kao što lamije doje svoju štenad golim sisama", pa je s toga pozvao kralja Andriju i ugarski episkopat, da ih unište. Kralj Andrija u to vreme nije mogao da deluje u Bosni, isto kao što nije mogao ništa preduzimati ni u Srbiji, zauzet unutrašnjim krizama. Jedino su Mađari uspeli, da 1125. god. Bosna bude podvrgnuta u crkvenom pogledu mađarskoj kaločkoj podbiskupiji. Papa je, odobravajući taj akt, pozvao nadbiskupa, da u svojoj novoj oblasti strogo deluje protiv jeretika i da protiv njih propoveda i pravi krstaški rat. Nadbiskup kaločki, Ugrin, pokušavao je doista, da preduzme nešto po želji papinoj i našao je i jednog vojskovođu, Jovana Anđela, sestrića mađarskog kralja Andrije, vizantiskog emigranta, koji je tada, sa majkom zajedno, bio gospodar Srema. Ali ozbiljne krize u Mađarskoj i posle sukobi s Bugarima nisu dozvoljavali ni Anđelu, kao ni drugim Mađarima, da se zapliću u bosanske stvari.

Narodnoj crkvi u Bosni zapreti veća opasnost tridesetih godina XIII veka. Prenestinski biskup Jakov beše 1233. god., kao papin legat, svršio jedan posao u Mađarskoj i onda stigao u Bosnu. Svojim velikim autoritetom, i političkim i crkvenim, on je uticao na tadašnjeg bosanskog bana Ninoslava da dade izjavu, da će on ostati u katoličkoj veri, iako su njegovi preci bili jeretici. Svojim pismom od 10. oktobra 1233. god. papa je Ninoslava, na osnovu te izjave, primio pod svoju zaštitu i garantovao mu integritet "pravom predragog mi u Hristu sina našeg svetlog kralja Ugarske". Ninoslavljev rođak Prijezda prešao je isto tako na katoličanstvo. Onima, koji su tad delovali u Bosni, taj sam čin pokrštavanja nije bio dovoljan kao jemstvo za njegovu ispravnost, nego su tražili nešto još neposrednije. Prijezda je morao dati svog sina za taoca, i kasnije je sam Ninoslav, uveravajući papu o njegovoj ispravnosti, trebao moliti čak u Rim da bude pušten. Kad se tako teški uslovi postavljaju članovima vladajuće kuće, i oni ih primaju, onda je nesumnjiv znak da onaj koji to traži pretstavlja neku neobičnu snagu. Verska aktivnost katolika u Bosni posle toga vrlo je živa. U Bosnu se, još iste godine, upućuje jedan poseban biskup, Johanes Vildeshauzen, rodom Nemac iz Frajburga. Dominikanski red, poznat kao vrlo oštar u proganjanju francuskih jeretika, dolazi isto tako, po papinoj naredbi, da deluje u Bosni. Legati rimski bivaju sve češći; Bosni se očevidno poklanja sve veća pažnja. Za nju se na papskoj kuriji govori, da zbog jeretika izgleda "kao pustinja i šikara, puka trnja i kopriva, i postala je leglo guja". Novi biskup ima toliko samosvesti i energije, da neće da vodi računa ni o željama mađarskog kralja, i sam papa mora da ga smiruje i, u interesu kurije, nagoni na popuštanja. Međutim, u zemlji postoji jak narodni otpor. Iz Rima se s toga, jednim pismom od 17. oktobra 1234. god., traži čista situacija u Bosni, i, ako ne pomogne drugo, preporučuje se krstaški rat. Hrvatskog hercega Kolomana papa Grgur IX izrično upućuje na tu dužnost, a kad se on odazvao, papa ga je, gornjeg datuma, uzeo pod svoju zaštitu kao vojnika Hristovog. U Rimu se ovoj ekspediciji davala tolika važnost, da su krstaši za Bosnu bili izjednačeni sa osloboditeljima Svete Zemlje. Takvo raspoloženje u Rimu izazivala je Ugarska, da bi ga posle mogla iskoristiti u svoje političke svrhe. Kralj Andrija je izlagao papi opasnost od nepouzdanih bosanskih banova i potrebu da se vlast nad Bosnom potpuno preda mađarskim kraljevima, koji se ne bi dozvoljavali da se u zemlji javlja sve ovo, što je sad u njoj. Papa je primio te sugestije Mađarske i 9. avgusta 1235. god. odobrio je kraljevu odluku, da Bosna pripadne Andrijinom sinu Kolomanu.

Koloman je i počeo rat u Bosni, u ime vere, a u stvari u ime svojih i mađarskih osvajačkih ciljeva. Ban Ninoslav, koji je raniju izjavu dao pod pritiskom, bio je pravi pretstavnik otpornih Bosanaca. Oni nisu hteli novu veru, koju su im donosili na mađarskom maču. Snaga Mađarske ovog vremena bila je vrlo velika. U ratnom pohodu protiv Austrije oni su 1235. god. digli vojsku, koja se, verovatno preterano, cenila na 200.000 ljudi, ali koja je bila silna ako je iznosila i polovinu tog broja. Ninoslavu nije bilo lako ni inače. U zemlji je jedan deo velikaša prišao Mađarima (n. pr. usorski knez Sibislav, sin inače nepoznatog bana Stepana), a drugi se plašio. On se s toga povlačio u svoje teško pristupačne planine i izbegavao otvorenu borbu. Zbog toga se ratovanje prilično oteglo. Mađari postigoše izvesne uspehe u Zahumlju i Zapadnim Stranama, ali prave, središnje Bosne nisu mogli osvojiti. God. 1238., 26. aprila, pisao je, istina, papa, da je Koloman uništio jeretičku napast; 23. decembra iste godine govorio je o "desnici Stvoriteljevoj koja triumfuje", ali svi ti uspesi, u koliko ih je bilo, behu kratka veka. Već 1240. god. dolazi ban Ninoslav bezbrižno u Dubrovnik i tu čak obećava Republici da će je uzeti u zaštitu, ako bi došlo do njenog sukoba s raškim kraljem. Kad dve godine posle rata s Mađarima Ninoslav uzima na se ulogu zaštitnika i izlaže se opasnosti, da uđe u jedan nov rat, znači: prvo, da njegov položaj u Bosni nije bio nimalo nesiguran i drugo, da mađarski udarci nisu naneli njegovoj državi tolike štete, da bi joj trebalo duže vremena za oporavljanje.