Iako su prijetili i upadali nekoliko puta, tek u proljeće 1448. godine Osmanlije su nakon zauzimanja tvrđave Hodidjed, uspostavile prvu stalnu posadu na području današnje Bosne i Hercegovine. Osnovale su provinciju Hodidjed i priključili je Skopskom "krajištu".
Petnaest godina kasnije, početkom svibnja 1463. godine, preko Skoplja i današnjeg Sandžaka osmanska je vojska došla do Drine i počela zauzimanje Bosanskog kraljevstva. Sultanu Mehmedu II uskoro se predao utvrđeni grad Bobovac, pa Visoko, pa Travnik, pa Jajce.
Kralj Stjepan Tomašević povukao se iz Jajca u tvrđavu Ključ. Nakon četverodnevne opsade predao se jer mu je Mahmut-paša zajamčio život. Odveden je u Jajce kod sultana, zapovjedio predaju svih gradova, a potom pogubljen od istog sultana koji mu je jamčio život.
Iste godine Osmanlije su osnovale Bosanski sandžak. Bosna je "šaptom pala", ali Hercegovina nije.
Do 1465. herceg Stjepan Vukčić Kosača uspostavio je apsolutnu kontrolu na području Hercegovine. Što diplomacijom, što ratovanjem, uspio je sačuvati zemlju od osvajača sve dok se pod pritiskom znatno jače osmanlijske vojske nije povukao u Novi. Herceg je umro 1466. godine, a Novi odolijevao Osmanlijama sve do 1482. godine kada ga je, Hercegov sin Vlatko Hercegović Kosača morao napustiti.
Drugi Hercegov sin, veliki vezir Ahmet paša Hercegović na osvojenim područjima Hercegovine utemeljio je sandžak Hercegovina.
Novi preustrojem carstva godine 1580. godine uspostavljen je Bosanski ejalet na čelu sa begler-begom. Prvotno je uključivao cijele današnje Hercegovinu i Bosnu, uključujući dijelove Hrvatske, Crne Gore i Srbije. Ujedinio je sandžake: Bosanski, Hercegovački, Kliški, Krčko-lički, Cernički (Pakrački), Zvornički i Požeški, Prizrenski i Vučitrnski.
Na čelo tek uspostavljenog pašaluka postavljen je Ferhad-beg Sokolović (1580–88). Bosanski beglerbeg nosio je naslov paše s dva ili tri tuga (konjska repa), a od početka 17. stoljeća često ima i naslov vezira.
Ejalet je više je puta teritorijalno uređivan. U 16. stoljeću vraćeni Prizrenski i Vučitrnski sandžaci vraćeni su Rumelijskomu ejaletu, osvajanjem Bihaća osnovan je Bihaćki sandžak. Početkom 17. stoljeća Požeški je sandžak pripojen Kaniškom pašaluku. U ratu su izgubljeni Cernički i Lički sandžaci. Ukinut je Bihaćki sandžak.
Početkom 19. stoljeća ukinuti su Kliški i Zvornički sandžak, a 1833 godine od Hercegovačkog sndžaka utemljen je poseban ejalet, Hercegovački pašaluk s vezirom na čelu.
Reorganizacijom iz 1851. godine ukinuti su sandžaci i kadiluci. Bosanski pašaluk podijeljen je na pet okruga (kajmekamluka): Sarajevski, Bihaćki, Banjalučki, Zvornički i Novopazarski, a Hercegovački pašaluk na tri: Mostarski, Pljevaljski i Trebinjski. Kajmekamluci su podjeljeni na na 44 mudirluka u Bosanskom i 14 u Hercegovačkom ejaletu.
Godine 1865. provedena je nova reorganizacija. Pašaluci Hercegovački i Bosanski ujedinjeni su u novu jedinicu uprave - vilajet na čelu s valijom. Novi vilajet je bio podijeljen na sedam sandžaka: Sarajevski, Travnički, Bihaćki, Banjalučki, Zvornički, Novopazarski i Hercegovački. God. 1872. iz Bosanskog vilajeta izdvojen je Novopazarski sandžak. Zbog rasplamsalog Hercegovačkog ustanka Hercegovački je pašaluk ponovno izdvojen pred početak austrougarske okupacije.
Prvih 59 godina sjedište Bosanskog pašaluka bilo je u Banjoj Luci (1580. - 1639. godine), potom 48 godina u Sarajevu (1639. - 1687. godine), pa punih 163 godine u Travniku (1687. - 1850. godine), te pred kraj osmanske vladavine opet u Sarajevu.
Sjedište Hercegovačkog pašaluka bilo je cijelo vrijeme u Mostaru.