Oslobođenjem Sarajeva 5. aprila 1945. godine, jedinice 2., 3. i 5. korpusa Jugoslavenske armije su nastavile goniti neprijatelja dolinom rijeke Bosne u pravcu Maglaja i Žepča. Za vrijeme borbi za Sarajevo u redove 16. muslimanske brigade pristupilo je oko 300 novih boraca, većinom sarajevskih ilegalaca – omladinaca. Pred pokret prema srednjoj Bosni, izvršena je smotra 7. aprila 1945. godine na Kovačima, iznad Baščaršije. Nakon predaha kod Semizovca brigada se sutradan sastala sa 27. divizijom.
Narednih dana brigada se preko Breze, Vareša i Careve Ćuprije prebacila u dolinu rijeke Krivaje, na prilaze Zavidovićima, gdje se nalazila glavnina njemačke 181. divizije. Nijemci su organizovali odbranu na prostoru tzv. Švapske mahale i u stambenim zgradama. Također, odbrana je organizovana i na desnoj obali rijeke Bosne, kod ušća Krivaje. Štab 27. divizije, kojem je pripadala i 16. muslimanska brigada, odlučio je da presiječe cestovnu komunikaciju Žepče – Zadivodići – Maglaj i zauzme Zavidoviće. Glavnina 16. muslimanske postavljena je u rejonu sela Žišci, Kovači i Hrkići. Međutim, pred napad izmjenjena je taktika tako da je glavnina brigade raspoređena na pravcu sela Stavci – k.380 – k. 199. Napad je počeo 12. aprila u jutarnjim satima i već pri prvom pokušaju ovladano je kotom 380, ali daljni prodor je zaustavljen uslijed žestokog njemačkog otpora. Napad je obnovljen u noći sa 13. na 14. april, prilikom čega su bataljoni 16. muslimanske brigade očistili niz kuća iz kojih su Nijemci pružali otpor kod ušća Krivaje u Bosnu, čime je omogućen prijelaz ostalim jedinicama JA preko mosta. Ipak, uslijed žestoke artiljerijske paljbe neprijatelj je zaustavio prijelaz preko mosta u grad. U kontranapadu Nijemci su vratili most te odbacili jedinice 16. muslimanske brigade iz Švapskog naselja. Time su jedinice 19. brigade JA ostale u okruženju u Zavidovićima. Da bi se pomoglo jedinicama koje su ostale u okruženju pokušan je prijelaz preko rijeke Bosne, ali se do svanuća 14. aprila uspjela prebaciti samo jedna četa 19. brigade JA. Glavnina 16. muslimanske brigade imala je zadatak da ponovo ovlada grupom kuća uz ušće Krivaje i da na juriš pređe most i uđe u grad. Kuće su zauzete ali prijelaz preko mosta nije realizovan niti nakon nekoliko pokušaja. Do kraja dana otpor Nijemaca je jenjavao. Tada iz pravca Žepča u ispomoć dolazi jedan bataljon 7. SS diviziji koji sa leđa napada pripadnike 20. brigade JA, nakon čega je ugrožena i linija rasporeda 16. muslimanske brigade. Ovim manevrom Nijemci su vratili sve mostove na rijeci Bosni i cestu od Krivaje do Žepča. Tim činom uspješno su izvučene i sve njemačke snage iz Zavidovića, poslije čega se Nijemci povlače prema Žepču i Maglaju. U borbama za Zavidoviće 16. muslimanska brigada je imala 26 mrtvih i 40 ranjenih boraca.
Oslobođenjem Zavidovića jedinice 16. muslimanske brigade se upućuju desnom obalom rijeke Bosne ka Maglaju. Međutim, neprijatelj nije odstupao desnom obalom Bosne, tako da su jedinice 16. muslimanske brigade bez otpora ušle u Žepče i Maglaj, a naposlijetku i u Doboj. Zbog raspada fronta u Hrvatskoj i Srbiji, veća grupacija četnika i ustaša se grupisala na području Trebave, Posavine, Majevice i Ozrena. U okviru toga 16. muslimanska brigada dobija zadatak da očisti područje Trebave. Poslije jednodnevnog odmora u Doboju, brigada se 19. aprila u dvije kolone upućuje prema Gradačcu i Modriči, gdje u naredna tri dana vrši izviđanje i čišćenje terena na Trebavi i dijelu Posavine. Štab 27. divizije 23. aprila naređuje 16. muslimanskoj brigadi da “izvrši pokret na Vučjak i da isti zaposjedne kako bi se jedinicama 25. divizije olakšala operacija na prostoru Potočani – Vlaška Mahala – Mrka Ada – Bačegovac”. Ipak, brigada je dobila naređenje da prije nego što se rasporedi na određenom prostoru, neutrališe grupu od oko 400 ustaša u Vlaškoj Mahali. Poslije kraćeg artiljerijskog napada jedinice 16. muslimanske brigade 23. aprila kreću u napad, ali su brzo zaustavljene i prisiljene na povlačenje. Zbog izrazito žestokog otpora i teške fortifikacije neprijatelja, u dogovoru sa 25. divizijom odlučeno je da se odustane od zauzimanja Vučjaka, a da glavnina 16. muslimanske brigade preuzme dio fronta 25. divizije kod Mrke Ade te da nakon popune snaga krene u napad. Poslije popune i kratke artiljerijske paljbe u poslijepodnevnim satima se kreće u napad i već pri prvom napadu jedinica zauzima Mrku Adu i prodire u Balegovac, ali uslijed otpora dalje nisu mogli. U večernjim satima neprijatelj prelazi u napad ali ga jedinice 16. muslimanske brigade odbijaju. Borbe su nastavljene sve do 25. aprila, ali ustaše su pružile žestok otpor koji nije savladan. Tada Stab 25. divizije, kojem je privremeno dodata i 16. muslimanska brigada, odlučuje da u večernjim satima izvrši silovit napad na ustaše u Vlaškoj Mahali. Brigada cijeli dan vodi žestoke borbe, a o intenzitetu svjedoči podatak da su neki položaji i po šest puta padali iz ruke u ruku. Da bi uspješno izvršila zadatak brigada dio snaga ubacuje u neprijateljsku pozadinu Vlaške Mahale, a glavnina je popunjena rezervom – 4. bataljonom. Tako je pred kraj dana, 25. aprila, cijela brigada prešla u silovit napad na ustaše. U žestokom sukobu teško je ranjen i komandant brigade, kapetan Spaso Mičić. Ipak, pored početnih uspjeha napad na Vlašku Mahalu nije dao rezultate. Naredna dva dana, 26. i 27. aprila, brigada je nastavila borbe na liniji Balegovac – Vlaška Mahala. Naređenjem štaba 2. armije, 25. divizija je 28. aprila počela napuštati položaje radi pokreta na novi zadatak, poslije čega je 16. muslimanska brigada preuzela njezin dio fronta u rejonu sela Potočani. Štabu brigade je bilo jasno da neće moći duže vremena držati nove linije. Sutradan 29. aprila krenuo je opšti napad oko 2 500 domobrana i ustaša na linije 16. muslimanske brigade. Poslije četiri sata borbi brigada je bila primorana da se povuče sa položaja kod Potočana, a povlačenje se odvijalo sve do skelskih prijelaza na rijeci Bosni, gdje su hrvatske snage konačno zaustavljene. U teškim borbama od 23. do 27. aprila 16. muslimanska brigada je imala oko 200 ljudi izbačenih iz stroja.
Prema naređenju Vrhovnog štaba, 16. muslimanska brigada je morala “svim sredstvima” zadržati položaje u rejonu Modriče na rijeci Bosni, dok ne stigne novo pojačanje. Zbog toga su vršeni iznenadni manji napadi na neprijatelja. Kada su 2. maja dio položaja preuzele jedinice 19. brigade JA, 16. muslimanska brigada je upućena na položaje kod sela Srnave do brda Lipe. Pošto se front skratio, Štab brigade je odlučio da u noći sa 2. na 3. maj zauzme mjesto Potočane. Napad je izvršen, ali su ustaše uspjele zadržati selo. Ipak, već sutradan je uz upotrebu artiljerije zauzeto mjesto, a ustaše su potisnute prema Prnjavoru i Vlaškoj Mahali. U toku ovih borbi brigada je imala 28 mrtvih i ranjenih boraca. Međutim, već sutradan (4. maja) ustaše su izvršile kontranapad nakon čega se brigada povukla iz Potočana prema brdu Lipi, ali je selo ponovo vraćeno nakon par sati borbe.
Nakon dolaska pojačanja, 16. muslimanska brigada poduzima napad prema Prnjavoru te ga zauzima, zajedno sa selom Bukovicom i dijelom sela Gornje Dubice. Novi kontranapad koji je uslijedio od strane ustaša doveo je do teških borbi za sam Prnjavor i razvio najtežu borbu u kojoj je 16. muslimanska brigada učestvovala još od Sarajevske operacije. Tom prilikom je brigada imala 18 mrtvih i 13 ranjenih boraca. Pošto prodor brigade nije uspio između Odžaka i Vlaške Mahale, Štab 27. divizije odlučuje da brigada nakon kratkog odmora izvrši obilazak i prodre u pozadinu ustaša, desnom stranom rijeke Save. Prvi ešalon brigade je u noći sa 6. na 7. maj bez borbe upao u sela Dubice i Prud. Ipak, uslijed ne ispunjavanja zadatka od strane 19. brigade JA, Štab je naredio da se 16. muslimanska brigada vrati na početne položaje. Štab 27. divizije je zaključio da konačno eliminisanje ustaša u Posavini, uključujući i najžešću tačku Odžak, nije moguće bez upotrebe teške artiljerije, avijacije i tenkova. S toga je odlučeno da se obustave napadi većih razmjera do pristizanja tehničkih sredstava.
