Razdoblje od početka XIII stoljeća pa do dolaska na vlast bana Mateja Ninoslava 1232 godine u Bosni je obilježeno jačanjem i širenjem Crkve Bosanske i njenog učenja, te naglim porastom moći i uticaja bosanske vlastele. Pritisci papske kurije na Bosnu, u cilju pokrštavanja Bošnjaka, ne gube na svom intenzitetu jos od Sabora na Bilinu polju gdje je papa tražio da se Kulin ban odrekne svog učenja ili u protivnom da se suoči sa križarskim ratom protiv Bosne i svog bošnjačkog naroda. Već 1233 godine papa upućuje u Bosnu novog papskog izaslanika,kardinala Jakoba. On je tu na prvom mjestu zatekao novog bana Mateja Ninoslava, Bošnjaka porijeklom iz heretičke porodice, kojega je vjerovatno i uz ugarski pritisak, prisilio da prihvati katoličanstvo. Skupa sa Ninoslavom na katoličku je vjeru prešao i njegov rođak Prijezda. Ninoslav je dominikancima, koji su kao misionari i inkvizitori ubrzo došli u Bosnu da pokrste Bošnjake, bio prisiljen predati i svoga sina kao taoca, čime je jamčio da neće odstupiti od rimske crkve. Ban Matej Ninoslav je 1233 godine pisao papi Grguru XI da se njegova vlastela ne pokorava, prema starom običaju,njegovoj vrhovnoj vlasti, nego samostalno upravlja povjerenim župama. Dok su njegovi preci, žalio se ban Ninoslav, “po starom običaju,” povjeravali župe i sela kome su htjeli i oduzimali ih prema vlastitom nahođenju i potrebi,sada njemu, “koji je nedavno sa heretičke prešao na katoličku vjeri i počeo da goni heretike,” držaoci posjeda “uskraćuju poslušnost, krše stare običaje” i zadržavaju posjede “protiv njegove volje.” 

Međutim, nakon izvještaja iz Bosne da je i sam ban Matej Ninoslav ponovno prišao hereticima i da je heretički pokret zahvatio i susjedne zemlje, posebno Slavoniju, papa je obnovio zahtjev da se protiv Bosne povede križarski rat. Papskom biskupu Ivanu Teutoncu naloženo je da u Bosni propovijeda “sveti

rat” protiv bosanskih i slavonskih heretika. Cijela križarska vojna povjerena je hercegu Kolomanu, koji je dobio posebna ovlaštenja. Ban Matej Ninoslav, suočen sa napadom na Bosnu i mogućim istrebljenjem Bošnjaka, nije oklijevao da se, bez obzira na vjerska pitanja stavi na čelo otpora protiv Rima i Ugarske.  Križarski “sveti rat” protiv Bošnjaka i njihovog vjerskog učenja počeo je 1235 i sa prekidima trajao tri godine. Kolomanova vojska uspjela je uz mnogo prolivene krvi proći kroz Bosnu  i Humsku zemlju. Kada se 1237/38 sa plijenom povukla iz Bosne, stvari su u Bosni opet krenule svojim uobičajenim tokom.Cilj istrebljenja heretizma kod Bošnjaka ipak nije uspio. Nadasve, imao je kontra-efekat, jer je na čelu otpora sa banom Matejom Ninoslavom ujedinio u otporu sve strukture bosanske države,uključujući tu i domaću crkvu, vlastelu, seljaštvo i vladara. Nakon odbrane zemlje od križara, ban Matej Ninoslav je proljeća 1240 zaključio ugovor sa Dubrovnikom o trgovini i prijateljstvu. Ban Ninoslav se obavezao ugovorom da će braniti Dubrovnik  ako bi zaratio sa raškim kraljem. Sve to pokazuje da je bez obzira na tek izdržani križarski rat, vojna snaga bana bila značajna, a njegova vlast čvrsta i postojana. Ban Matej Ninoslav je 1243/44 sa jačom vojskom otišao u Split i pomogao u ratu protiv Trogira koji je bio odan Ninoslavovom političkom protivniku,ugarsko-hrvatskom kralju Beli IV. Već 1244 kralj Bela IV. poveo je kazneni pohod protiv bana i prisilio ga da oda svoju lojalnost ugarskom kralju i prizna bosanskoj biskupiji prava i povlastice na ranije datim posjedima (radi se o posjedima koji su dodijeljeni katoličkoj biskupiji u Bosni poslije Sabora na Bilinu Polju). Posljednje spominjanje bana Mateja Ninoslava potiče iz 1249 kada je opet u punoj snazi obnovio svoj raniji trgovački ugovor sa Dubrovnikom.