Dolaskom Topal Osman paše na mjesto bosanskog namjesnika 1861. godine uveliko se počelo govoriti i o organizaciji “ovdašnje muslimanske narodne vojske”. O tome se pričalo i u narodu, ali i među stranim konzulima. U proljeće 1864. godine Osman paša je upoznao osmanskog sultana Abdul Aziza sa ovim projektom. Prema njegovom planu trebao se formirati jedan vojni puk od Bošnjaka – muslimana u jačini od 4 000 ljudi, kojeg bi činilo samo stanovništvo Bosne, bez Hercegovine i Novopazarskog sandžaka. Vojna služba bi trajala tri godine. Vojska je trebala imati drugačiju uniformu od standardne narodne nošnje, savremene puške, dok bi polovicu oficira činili domaći ljudi, dakle Bošnjaci a drugu osmanski oficiri. Bio je to prvi projekat formiranja jedne bosanske vojske nakon propasti Kraljevine Bosne 1463. godine. Osman paša je smatrao da bi kroz prolaženje opće vojne obuke, koja bi trajala tri godine, znatan broj domaćeg stanovništva stekao osnovno vojno znanje. Sam zadatak vojnog puka je bio da isključivo brani granice Bosanskog ejaleta.
Koliko je Osman paši bilo bitno da što prije sprovede organizaciju vojnog puka svjedoči i dolazak osmanskog generala Salih paše 17. avgusta 1864. godine u Sarajevo. Uskoro je počelo i popisivanje za vojsku a do polovine septembra je regrutovano oko 300 mladića, uglavnom dobrovoljaca. Plan je podrazumijevao da se kroz deset godina regrutuju mladići u dva pješadijska puka od po tri bataljona, što bi značilo da bi bosanska vojska u konačnici imala deset domaćih pukova sa kojima bi bila u stanju da suzbije bilo koju agresiju iz Srbije ili Crne Gore. [bosnae.info]
U proces regrutiranja bošnjačkih mladića osmanska Porta uključila je i niz drugih važnih osmanskih dostojanstvenika. Među najvažnijim je Ahmed Dževdet paša koji je u Bosnu došao još u decembru 1863. godine sa ciljem da privoli Bošnjake da i oni, kao i stanovnici ostalih dijelova Osmanskog carstva, prihvate regrutiranje mladića u redovnu vojsku. Zbog toga je Ahmed paša sazvao i najuglednije ljude sa prostora Bosanskog ejaleta i sa njima dogovorio da se nova vojska zove narodna i da neće nikada ići izvan Bosne. Hatib Begove džamije Hafiz efendija, je organizaciju narodne vojske prokomentarisao na slijedeći način: “Mi tražimo da bosanska vojska nosi uniforme sa zelenim širitima, onako kako je obučena vojska koja je došla na Bajram ujutro u džamiju”. Razlog tome je što su Bošnjaci imali veliku slabost prema zelenoj boji i jer se u “bosanskom govoru zeleno upotrebljava u značenju: slavno i časno”. Ovo je prihvaćeno, pa je i u Bosanskom ejaletu otpočeo proces regrutacije za osmansku vojsku u trajanju od tri godine, dok je u ostalim dijelovima vojni rok trajao pet godina.
Nakon dogovora sultan Abdul Aziz je dostavio ferman kojim potvrđuje formiranje bosanske vojske. Prilikom objavljivanja ovog fermana Ahmed paša je izjavio: “Bošnjaci su veliki rodoljubi, a njihova uloga u odbrani domovine i postojani karakter su nemjerljivi (…) Bosna liči na jednu knjigu u kojoj se bio pokvario povez, no pri tom njenom sadržaju, njeni se listovi nisu raskupusali i rasturili. Čim se ta knjiga bude uvezala, ona će postati i biti ona stara knjiga. A te korice, taj povez, jeste ovaj uzvišeni ferman”. Jedan od bošnjačkih velikaša, Uzun Abdulah je u ime naroda odgovorio: “Gospodine, narod kaže: Mi do te mjere ne možemo reći da zaslužujemo pohvalu koju ste nam upravili, ali mi vama, za takvo mišljenje o nama ipak, ovako svi na okupu zahvaljujemo i pri tom napominjemo da u kvarenju poveza i u njegovoj opravci mi nismo imali nikakvog učešća. Ako do koga ima krivice, svakako će biti do knjigovesca.”
