Ali novoprobuđena ambicija više nikada nije nestala. Tzv. privatne špijunske istrage protivničkih kriminalnih gangova postat će jedna od specifičnosti Žuljevićeve postrojbe HVO-a koja je nakon raspada Herceg Bosne počela preuzimati zagrebačko podzemlje, ionako pod kontrolom raznih službi hrvatske obavještajne zajednice. Uživljen u konspirativnost, Žuljević će od Srba ishoditi dokumente u Republici Srpskoj na ime Mišo Mišić koji će mu u mirnodopskom razdoblju poslužiti za kontakte sa srpskim ratnim zločincima i kriminalcima." U hrvatsko-srpski rat, kao vojnik, uključio se u kolovozu 1991. Postao je pripadnik 4. splitske brigade, koja je ratovala u zaleđu dalmatinskih gradova. Kako nije sudjelovao u spektakularnim ratnim akcijama protiv JNA, Žuljević se iz tog razdoblja najradije sjeća sela Čavoglave, gdje je prvi put, jedne noći oko logorske vatre, čuo budući hit tada nepoznatog Marka Perkovića zvanog Thompson, koji je svoj kasniji status zvijezde desnog krila hrvatske estrade osvojio zahvaljujući maskirnoj uniformi dobrovoljca Domovinskog rata.
Teritorij Republike Hrvatske napustio je tri mjeseca nakon njenog međunarodnog priznanja, u travnju 1992. Kao dobrovoljac koji se samoinicijativno vraća u zavičaj da bi ratovao protiv JNA i Srbije, Žuljević je poslan u Bugojno gdje se već uvelike pripremala realizacija zaključaka s tajnog sastanka Franje Tuđmana s prvacima HDZ-a BiH iz jeseni 1991.9 Na spomenutom sastanku eksplicitno je dogovoreno pripajanje tzv. hrvatskih povijesnih prostora u BiH Republici Hrvatskoj. Žuljeviću je rečeno da u gradu postoji ekskluzivno hrvatski krizni štab, da su lokalni Hrvati dobro naoružani, da su trupe JNA prilično slabašne i da se, ukratko, očekuje samo dobar povod za ucrtavanje novih hrvatskih granica. Razočaran, otkrio je da su stvari na terenu potpuno drukčije: u bugojanskoj općini nakon prvih višestranačkih izbora vlast jest osvojio HDZ, ali uz pomoć muslimanskih glasova, JNA je još uvijek čvrsto stolovala u kasarnama, a jedini pokret otpora bio je koncentriran u Teritorijalnoj obrani pod zajedničkim hrvatsko-muslimanskim zapovjedništvom lokalnih ogranaka HDZ-a BiH i SDA u osnivanju.
Ono što je Žuljević poduzeo može se definirati kao zametak hrvatske “pete kolone” u suverenoj državi. Kako će sam poslije pripovijedati, regrutirao je tridesetak Bugojanaca, s podebljim policijskim dosjeima, obukao ih u maskime uniforme, zalijepio na njih oznake Hrvatske vojske i proglasio ih prvom, elitnom oružanom jedinicom Republike Hrvatske u srednjoj Bosni.
Amblemi Hrvatske vojske, istina, zamijenjeni su nakon tjedan dana znakovima HVO-a, oružane sile Hrvatske zajednice Herceg Bosne koja je samo deklarativno priznavala postojanje šire domovine Bosne i Hercegovine. Naziv “Garavi” dali su im seljaci, koji u tom predratnom metežu nacionalnih formacija i njihovih frakcija doista više nisu shvaćali tko koga predstavlja, tko koga zagovara i tko što namjerava. Žuljevićevi ljudi bili su prepoznatljivi po tome što su se, skrivajući identitet, u Uskoplju i Bugojnu pojavljivali crno oslikanih lica. Kamp su uredili u napuštenom pastirskom selu Okolišće u nepristupačnoj planinskoj zabiti bugojanskog kraja. Već tu je, navodno, Žuljević postao izvrstan strijelac iz svih vrsta oružja.
Prva dva mjeseca nakon osnutka “Garavi” su ratovali protiv Srba. U suradnji s hrvatsko-muslimanskom Teritorijalnom obranom, zauzeli su bazu JNA u Zijametu. Nešto kasnije asistirali su HV-u u borbama na Kupresu koje su se pretvorile u masovni pokolj pre-živjelih branitelja Vukovara. Nakon hrvatskog poraza Kupreška visoravan, strateški važna poveznica Hrvatske i srednje Bosne, sve do 1994. bila je pod srpskom kontrolom. Prema općem mišljenu hercegbosanskog javnog mnijenja - ono je događaje ocjenjivalo potpuno drukčije od hrvatske javnosti - na Kupresu je Žuljević dva puta demonstrirao zavidnu hrabrost. Te 1992. predvodeći “Gara-ve” pobio je iz zasjede neku četničku skupinu srbijanskih dobrovoljaca koji su sami sebe prozvali “Bela rada”, a u drugoj bici za Kupres 1994., u izravnom okršaju s neprijateljem, izgubio je nogu i postao teški invalid.
Rat s Muslimanima počeo je za Žuljevića mnogo prije otvaranja sveopćeg hrvatsko-muslimanskog krvoprolića u prosincu 1992. Šest mjeseci prije, u lipnju 1992., Žuljevićeva postrojba, što je bio prvi zabilježen slučaj hrvatsko-muslimanskog okršaja, sudarila se s dojučerašnjim saveznicima iz Teritorijalne obrane kod Gornjeg Vakufa. Kontrolirajući prometnicu, zapovjednici TO-a izdali su nalog da se Žuljevićevi ljudi, kao paravojna, neregularna formacija, izvan kontrole njihova štaba, zaustave na kontrolnom punktu i razoružaju. Prinuđeno im je da skinu oznake HVO-a i da se priključe TO-u. “Garavi” su uzvratili vatrom; u puškaranju su pale i prve žrtve, poginuo je Žuljevićev zamjenik. Kao preuranjeno provociranje hrvatsko-muslimanskog raskola, incident je nekako zataškan. Premda su propagandno-psihološke pripreme već uznapredovale, u Zagrebu se procjenjivalo da situacija za novi rat još nije sasvim zrela.
Time se Žuljevićevo puškaranje s TO-om u lipnju 1992. mnogo više reflektiralo na odnose unutar samog HDZ-a BiH. Na javnoj razini strankom je predsjedavao Stjepan Kljuić, zagovornik nepodijeljene i multinacionalne BiH i obrambenog hrvatsko-muslimanskog savezništva, najprije u formi TO-a, a onda Armije BiH. Pod sve snažnijim utjecajem emisara iz Hrvatske, u stranci su se umnožavali njegovi politički protivnici koji su, poput Vinka Žuljevića Klice, u raspadu SFRJ vidjeli šansu za temeljito etničko čišćenje tzv. hrvatskih povijesnih područja. Doduše, ni ta frakcija nije zadugo ostala jedinstvena. Do 1995. i Daytonskog sporazuma ona se raspala na struje koje su se žestoko sporile oko veličine i opsega tog mitskog “hrvatskog povijesnog prostora” u Bosni i Hercegovini. Hrvati iz srednje Bosne zahtijevat će da se Hrvatskoj, zajedno s Hercegovinom, anektiraju dijelovi u kojima oni žive. Hercegovci će, naprotiv, smatrati da je samo njihovo zavičajno područje, kao najbliža granična zona, “prirodni” dio matičnog hrvatskog teritorija.
Kada je u rujnu 1992. završeno naoružavanje i ustrojavanje HVO- a, “Garavi” su svrstani u kategoriju specijalnih jedinica koje, primamo, obavljaju revolucionarno-političke zadaće. Prema mostarskim planovima, prvi cilj te “revolucije” nisu bili Muslimani ¡Teritorijalna obrana, nego Kljuićevi sljedbenici u HDZ-u BiH koji su na prvim slobodnim izborima osvojili vlast u gradovima i naseljima s hrvatskom većinom. U maskirnim uniformama, naoružani automatima, “specijalci” su iz općinskih i gradskih ureda fizički protjerivali predstavnike i činovnike općinskih uprava, zamjenjujući ih mostarskim namjesnicima HVO-a. Žuljević i njegovi “Garavi” na isti su način u Bugojnu Vladu Šoljića, izabranog predsjednika općine, promovirali u lokalnog vojno-civilnog diktatora koji je, raspustivši općinsku, višenacionalnu skupštinu, bugojansko područje proglasio dijelom “hrvatskog povijesnog prostora”.
Nakon osvajanja vojarne JNA u Zijametu i Šoljićeva ustoličenja u apsolutnog bugojanskog gospodara, Žuljevićevu postrojbu nikakva sila više nije mogla uklopiti u vojnu hijerarhiju HVO-a. Prema javno poznatim slučajevima iz tog vremena sve identične specijalne postrojbe rabile su, uostalom, iste argumente u očuvanju statusa autonomnih hajdučkih družina: budući da su okupljene kao dobrovoljačke skupine čiji su pripadnici sami sebe naoružavali i obučavali, smatralo se da imaju pravo na apsolutnu slobodu djelovanja. Pokušaji njihova discipliniranja uvijek su završavali incidentima na rubu internog rata između “specijalaca” i standardnih formacija HVO-a. Uskoro su maltretirali civilno stanovništvo svih nacija, pljačkajući, ubijajući, ucjenjujući. Policija ih nije mogla zaustaviti, čak i da je htjela. Bili su sve brojniji i sve bolje naoružani.
