Prije nego što će biti postavljen na mjesto bosanskog namjesnika Gazi Husrev beg dolazi na mjesto smederevskog sandžak bega 1519. godine. Smederevski sandžak je bio isturena oblast na granici prema Ugarskoj iz kojeg su Osmanlije često vršile pohod prema zapadu. Nemamo puno podataka o njegovom upravnjaju u ovom sandžaku, osim podatka da je imao prihod od 500 000 akči. Prve konkretne podatke dobijamo 1521. godine kada je osmanski sultan Sulejman Veličanstveni poduzeo pohod na Beograd. Bio je to prvi vojni pohod najslavnijeg osmanskog sultana, koji je Beograd nazvao “kapijom srednje Evrope”. Naime, da bi ostvario pohod prema srednjoj Evropi i dalje prema Budimu, Pešti i Beču bilo je neophodno zauzeti Beograd. Za ovu akciju angažovane su ogromne snage, a naređeno je i bosanskom i smederevskom sandžak begu da sa svojim trupama upadaju na prostor Hrvatske i Srijema. Sultan Sulejman je kao prethodnicu napada na Beograd poslao svoje istaknute ratnike Mehmed bega Mihaloglua i Hasan bega Turhanbegovića, dok je iz Istanbula upućeno i 1 000 janjičara koji su se u Smederevu trebali priključiti Gazi Husrev begu u opsadi Beograda. Tom prilikom Gazi Husrev beg je pripremio 15 000 vojnika za ospadu grada.

Husrev begova uloga u osvajanju Beograda je veoma značajna, jer su uz njega zajedno bili tadašnji rumelijski beglerbeg Ahmed paša, bosanski sandžak beg Bali beg Jahjapašić, te veliki vezir Piri Mehmed paša, a i već ranija konstatacija da mu je Sulejman lično u susret poslao 1 000 svojih janjičara dovoljno svjedoči tvrdnji. Nakon što je veliki vezir 7. jula 1521. godine osvojio Šabac, sutradan je došao i sultan Sulejman i izdao naredbu da se preko Save izgradi most preko kojeg bi vojska prešla u Srijem. Da bi lakše zauzeo Beograd sultan je osvojio skoro cijeli Srijem, dok je Gazi Husrev beg 12. jula zauzeo Zemun, poslije čega je sultan krenuo u opći napad na Beograd. Treba naglasiti da je Gazi Husrev beg pregovorima sa Markom Skoblićem, koji je sa 400 vojnika branio Zemun, uspio dogovoriti predaju Zemuna čime su spašeni brojni životi. Iako osmanske hronike najveću zaslugu opsadi Beograda prepisuju velikom veziru Piri Mehmed paši, iz jednog osmanskog dokumenta koji se čuva u Arhivu Topkapi muzeja u Istanbulu, se vidi da je Gazi Husrev beg 27. juna 1521. godine uspio blokirati sve prilaze Beogradu i da je pripremajući opsadu 3. jula 1521. godine došao pod Beograd. Prema navodima Pečevije sultan je naredio da vojska ide prema Budimu ali se tome usprotivio veliki vezir, smatrajući da nije dobro ostaviti važnu utvrdu kao što je Beograd bez glavne opsadne vojske. Međutim, dobio je naredbu da dođe u Šabac, iako je već opkolio Beograd. Nakon što je shvatio da teško bilo šta može uraditi dok se ne osvoji beogradska tvrđava, dobio je saglasnost od sultana da sa vojskom krene prema Beogradu sa obala Save. Njegova desna ruka u tom poduhvatu je bio Gazi Husrev beg. U konačnici Beograd je zauzet 30. avgusta 1521. godine. Prema svjedočenju jednog od učesnika bitke u grad su prvo ušli janjičari te na tvrđavli postavili zastavu i proučili ezan. Odmah nakon toga istaknuta je zastava smederevskog sandžak bega Gazi Husrev bega, čija je vojska naišla za janjičarima. Prema nekim navodima vojni orkestar Gazi Husrev bega je prvi zasvirao u osvojenom Beogradu. Sultan Sulejman je u Beograd ušao isti dan kada je zauzet, a kako je sutradan bio petak klanjana je i prva džuma u džamiji koja je napravljena u Donjoj crkvi.

O osvajanju Beograda zanimljive podatke navodi i poznati putopisac Evlija Ćelebija. On također navodi Gazi Husrev begove zasluge u zauzimanju Beograda: “U grad su najprije ušli zagradži baša od janjičarskog odžaka, smederevski sandžakbeg Husrev – beg i bosanski beg Kučuk Bali – beg. Pošto su zauzeli skladište municije (džebhane) i riznice (hazine), proučen je muslimanski ezan sa gradskih kula i bedema. I premda je vojska počela da ulazi u grad, neprijatelj zlotvor opet se nije okanio lukavstva, nego je, da bi u toj gužvi i neredu nanio veće gubitke muslimanskoj vojsci, opalio topove sa grada sa kojeg je tražio milost i zadao teške gubitke muslimanskoj vojsci. Na to je vojska u gomilama ušla u Beograd i neke Srbe pobila, a neke rastjerala. U četvrtak, 26. ramazana 927 (= 30. avgusta 1521) godine dovršeno je osvajanje Beograda”.

Osvajanjem Beograda svo novoosvojeno područje priključeno je Smederevskom sandžaku i pored činjenice da je Beograd zauzimao toliku teritoriju da se mogao oformiti zaseban sandžak. Na carskom divanu održanom 15. septembra 1521. godine pod Beogradom izvršena je smjena na čelu Smederevskog sandžaka. Prije nego što će krenuti u novi pohod, sultan Sulejman je Bali Begu Jahjapašiću dodijelio upravu nad Smederevskim sandžakom sa sjedištem u Beogradu, dok je na Bali begovo mjesto u Bosnu – Sarajevo, premješten Gazi Husrev beg, zbog zasluga prilikom zauzimanja Beograda.