Potpisivanjem Pariškog sporazuma 1856. godine Kneževina Srbija je otpočela pripreme za uspostavljanje potpune neovisnosti od Osmanskog carstva. U tu svrhu bilo je neophodno, pored uklanjanja osmanskih vojnika, realizirati i cilj iseljavanja muslimanskog življa sa teritorije Kneževine Srbije. Ovaj plan je ubrzan dolaskom Mihaila Obrenovića 1860. godine na mjesto srpskog kneza. U konačnici na konferenciji u Istanbulu, održanoj 1862. godine Kneževina Srbija i Osmansko carstvo su potpisali protokol kojim je odlučeno da se muslimani isele iz Srbije. Prema potpisanom protokolu odmah je počelo iseljavanje muslimana koji su živjeli na prostoru Beograda, Smedereva, Šapca, Sokola, Užica i Kladova. Oni muslimani koji su se osjećali Bošnjacima i koji su govorili bosanskim jezikom, iselili su se u Bosnu. Najveći dio muslimana koji je živio u Beogradu nastanio se na prostoru Niša, oni iz Smedereva i Kladova na prostoru Vidina, dok se kompletan živalj Užica, Sokola i Šapca naselio na prostoru Bosanskog ejaleta, tačnije na prostoru Zvorničkog sandžaka. Sultanovom naredbom iz proljeća 1863. godine za ove muhadžire je podignuto šest novih naselja.
Prilikom iseljavanja muslimani su zapali u velike teškoće. Srbi su 8. septembra 1862. godine zapalili čaršiju u Užicu, a za požar su optuženi muslimani. U požaru je stradala i pokradena sva imovina muslimana Užica. Kneževina Srbija je takvo stanje iskoristila da čim prije sprovede iseljavanje muslimana na prostor Bosanskog ejaleta. Stanovništvo Sokola se u početku nije željelo iseliti. Bosanski namjesnik Šerif Osman paša je narodu Sokola 13. oktobra 1862. godine poslao pismo u kojem ih savjetuje da se radi vlastite sigurnosti čim prije isele iz Sokola. Za prijevoz stanovnika Sokola obezbijedio je brodove, nakon čega su se muslimani Sokola 15. novembra 1862. godine iselili. Isto su učinili i muslimani Šapca sedam dana kasnije, prešavši rijeku Savu kod Brčkog. Time je u oktobru i novembru 1862. godine okončano iseljavanje muslimana iz Kneževine Srbije.
U podnesku od 18. novembra 1862. godine Šerif Osman paša navodi da je u Bosnu pristiglo 1 300 porodica sa više od 7 000 članova. Već u proljeće su im napravljene prve kuće u koje su se smjestili. Posjedi Husein kapetana Gradaščevića su određeni za najpovoljnije mjesto na koje će se muhadžiri smjestiti. Donesena je naredba da se izgradi između 600 i 700 kuća, a nakon izvršenih priprema i raspodjele zemlje zaključeno je da će ostati dovoljno zemljišta za izgradnju kasabe od 200 domaćinstava i nekoliko sela sa po 30 do 40 kuća. Također, predviđeno je da svako domaćinstvo dobije između 40 i 100 dunuma zemlje za obrađivanje. Ipak, dolaskom novog broja muhadžira ustanovljeno je da predviđeni prostor neće biti dovoljan za izgradnju svih kuća. Kako bi se riješio ovaj problem Šerif Osman paša je predložio državnim vlastima da se posjedi ranijih ljudi, koji su umrli a za sobom nisu ostavili nasljednika, iskoriste za izgradnju novih kuća. Kako je i bilo predviđeno, u proljeće 1863. godine, otpočela je izgradnja novih kasaba. Prilikom izviđanja terena Osman paša se u aprilu 1863. godine sastao se bosanskim mufetišom Dževdet pašom u Brčkom te je nakon razgovora sa njim, 10. maja 1863. godine upućen podnesk vladi u kojem je stajalo da će u toku narednih 20 dana biti pripremljen materijal za izgradnju kuća.
U novom podnesku od 21. juna 1863. godine, Istanbul je obaviješten “da je u mjestu Orašje, koje se nalazi uz rijeku Savu, predviđena izgradnja do 300 kuća. Na ušću rijeke Bosne u Savu, na četiri sata od Orašja, sa desne strane nalazi mjesto Šamac. Država će u ovom mjestu stanovnicima, kao zamjenu za izuzetu zemlju, dati imovinu na drugom mjestu gdje će biti izgrađeno do 300 kuća. U Banjalučkom sandžaku, na pola sata od rijeke Save, nalazi se selo Orahovo čija je zemlja izuzetno plodna, a koju vlasnici ne obrađuju. U selu Orahova će se za muhadžire iz Sokola napraviti 100 kuća. U selu Kostajnica, koje pripada kadiluku Kozarac u Bihaćkom sandžaku, biće sagrađeno 200 kuća. U selu Brezovo Polje koje pripada Bijeljinskom kadiluku u Zvorničkom sandžak izgradit će se 350 kuća. U čiftluku Kozluk koji je ostao od preminulog Osmana Mazhar paše, koji se nalazi u Zvorničkom kadiluku, bit će podignuto 100 kuća.” Dalje je navedeno da će Kostajnica, Šamac, Orašje i Brezovo polje biti podignute u rang kasabe, dok će Orahova i Kozluk biti izgrađeni kao sela.
U jesen 1863. godine Šerif Osman paša je krenuo na putovanje kako bi ustanovio do kojeg stepena je došla gradnja kuća i osnivanje kasaba. U izvještaju kojeg je dostavio 10. novembra 1863. godine navodi: “Kozluk: Kozul je čifluk Osman Mazhar paše(…) Ovdje je završena izgradnja kuća u koje je useljeno 120 muhadžirskih domaćinstava iz Sokola (…); Brezevo polje: Osman Šerif paša je, krečući se iz Kozluka, stigao u Brezovo polje koje pripada kadiluku Bijeljina (…) Parcele na ovim mjestima su, uslijed toga što nije bilo onih koje pripadaju državi, uz pristanak njihovih vlasnika zamijenjene za druge odgovarajuće parcele. Na kraju, okončana je gradnja 300 kuća za muhadžire iz Šapca i Užica, i ove porodice su se već uselile u novoizgrađene objekte; Orašje/Donja Azizija: Slijedeća stanica od Brezovog polja je Orašje (…) Ovdje je, kako je i planirano, okončana gradnja 200 kuća uglednih muhadžira iz Beograda, Užica i Šapca, te je izvršeno i njihovo useljavanje. Pošto je raspoloživo zemljište bilo nedovoljno za poljoprivredu, parcele pored njih su postpukom razmijene uzete od vlasnika i podijeljene muhadžirima; Šamac/Gornja Azizija: Na četiri sata iznad Orašja (…) Pošto je ovaj prostor bio pogodan za izgradnju kasabe napravljene su kuće u koje je useljeno 250 muhadžira iz Užica i Sokola… Naseljenim muhadžirima dodijeljen je i dio obradive zemlje (…); Orahovo: Zbog pozicije koju zauzima, u Orahovu je za 225 muhadžira iz Sokola osnovano prilično veliko selo koje je sačinjavalo pet mahala. U ovom mjestu kuće su potpuno završene, naseljavanje okončano, a potrebna zemlja data na obradu; Kostajnica: Stanica nakon Orahova… Nekada se ovdje nalazila velika kasaba koja je s vremenom u potpunosti propala. Iz razloga što je ovo mjesto pogodno za trgovinu u njemu je završena izgradnja kuća i naseljeno je 180 porodica muhadžira iz Užica (…)”.
Na ovaj način, za muhadžire Užica, Sokola, Šapca i Beograda, u Bosanskom ejaletu izgrađeno je 6 naseobina – 4 kasabe i 2 sela za manje od jedne godine. Velika većina muhadžira se u ovom periodu tu trajno nastanila. Pitanje imovinskog poravnjanja između Osmanske države i Kneževine Srbije je zaključeno sporazumom od 17. decembra 1865. godine, pa je zbog toga izgradnja novih kuća finansirana uglavnom od strane Osmanske države i muslimanskog stanovništva Bosne, koje se ujedinilo da bi zajednički pomoglo prognane Bošnjake.
