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.“

Ali već 1233. papa upućuje u Bosnu svog novog izaslanika, kardinala Jakoba jer ban podržava krstajne. Jakob je bana Ninoslava 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 došli u Bosnu 1234. morao dopustiti da pokrste Bošnjake, bio prisiljen predati i svoga sina kao taoca, čime je jamčio da neće odstupiti od rimske crkve. Ban Matija Ninoslav je pisao papi Grguru IX da se njegova vlastela ne pokorava 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 osobnom nahođenju i potrebi, sada njemu, „koji je nedavno sa heretičke prešao na katoličku vjeru i počeo goniti 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 Matija Ninoslav ponovno prišao krstjanima i da je Crkva bosanska zahvatila 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 krstjana. Cijela križarski pohod povjeren je hercegu Kolomanu (1102.-1141.), bratu ugarskog kralja Bele IV, koji je dobio posebna ovlaštenja. Ban Matija Ninoslav, suočen s 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 rat protiv Bošnjaka počeo je 1235. i sa prekidima trajao tri godine. Kolomanova vojska uspjela je uz mnogo prolivene krvi proći kroz Bosnu i Hum. Kad se 1237.-1238 s plijenom povukla iz Bosne, stvari su u Bosni opet krenule svojim uobičajenim tokom. Cilj istrebljenja krstjana ipak nije uspio. Nadasve, imao je kontraefekt, jer je otpor s banom Matijom Ninoslavom na čelu ujedinio sve strukture bosanske države, uključujući tu i domaću crkvu, vlastelu i seljaštvo. Od bosanskih velikaša jedino je knez Usore Sibislav bio uz križare i zbog toga ga papa naziva ljiljanom među trnjem. U svakom slučaju knez Sibislav nije protiv bana Ninoslava ratovao zbog vjerskog uvjerenja (pošto je i tada, a i kasnije Ninoslav bio katolik, a nikad iskren krstjanin) već isključivo zbog toga što je želio za sebe bansku čast.

Nakon odbrane zemlje od križara, ban Matija Ninoslav je u proljeće 1240. zaključio ugovor s Dubrovnikom o trgovini i prijateljstvu. Ban Ninoslav se obavezao tim ugovorom da će braniti Dubrovnik ako bi Republika Sv. Vlahe zaratila 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 Matija Ninoslav je 1243.-1244. s vojskom otišao u Split i pomogao u ratu protiv Trogira koji je bio odan Ninoslavovom političkom protivniku, ugarsko-hrvatskom kralju Beli IV (1235.-1270). Već 1244. kralj Bela IV poveo je kazneni pohod protiv bana i prisilio ga da 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 1250. kad je opet u punoj snazi obnovio svoj raniji trgovački ugovor sa Dubrovnikom.

Za Matiju Ninoslava se zna da je bio u srodstvu s Kulinom banom, ali nije utvrđeno u kojem stupnju srodstva.