Koristeći se iskustvima iz drugih krajeva tadašnje države, u Mostaru je, početkom 1922. godine, prihvaćena inicijativa za osnivanjem radničkog sportskog društva koje bi kako okupljalo radnike i druge ljubitelje nogometa u Mostaru, tako i predstavljalo jedan od snažnih punktova za jačanje radničke klase i borbe za njena radnička i socijalna prava.
Sama inicijativa potekla je od Gojka Vukovića, revolucionara i uglednog građanina Mostara koji je u tom periodu uživao veliki autoritet, ne samo među radnicima nego i kod ostalih građana.
Tako su u ljeto 1922. godine na poljani kod Sjevernog logora, u zakazano vrijeme, okupljenim radnicima i đacima mahom Učiteljske škole pročitana prva Pravila kluba kao i imena predviđenih rukovodilaca.
Osnivačka skupština novoformiranog Radničkog sportskog društva održana je 26. juna 1922. godine te su istog dana vlastima na verifikaciju predata i Pravila kluba radi zakonom predviđenog odobrenja, te historija fudbalskog kluba Velež iz Mostara počinje 26. juna 1922. godine.
Kada se raspravljalo o imenu kluba, bilo je više prijedloga, ali kada je predloženo ime obližnje planine Velež, jednom od simbola Grada i Hercegovine, prisutni su se pogledali i nakon što je jedan od prisutnih glasno izrazio svoju saglasnost i ostali su prihvatili ime Velež.
Prvi dresovi bili su bijele i crne boje, a razlog za to bila je neimaština, a u dresovima crvene boje nogometaši Veleža zaigrali su tek 1925. godine, i u Mostar ih je iz Zagreba donio tadašnji član Uprave Vaso Pucarić.
Prvu Upravu kluba činili su Anđelko Vlaho (predsjednik), Ranko Slijepčević (potpredsjednik), Borivoje Janjoš (prvi sekretar), Ljubomir Basta (drugi sekretar), Rudolf Beltram (blagajnik), te članovi Nadzornog odbora Mihajlo Cvetković, Milan Pavić i Bogdan Tepšić, a prvi kapiten Kluba bio je Lazar Radić.
Nakon osnivanja i odobrenja klupskih pravila, Velež igra prijateljske utakmice, i startovao je sa ekipom: Marko Vučijak, Ljubo Zrimšek, Savo Turanjin, Mile Pavić, Lazar Radić, Milan Rajković, Bogdan Tepšić, Ranko Slijepčević, Branko Turanjanin, Savo Medan i jedan još nepoznat čovjek iz Srbije, koji je u Mostaru tražio posao.
U svojim prvim danima Velež je odmjeravao snage s lokalnim rivalima, ali i onima iz drugih gradova, a godine 1924. bio je finalist olimpijskog turnira u Mostaru.
Već u sezoni 1934/35. ubrajao se među kvalitetnije bosanskohercegovačke klubove, međutim, Veležu je privremeno zabranjivan rad.
Još okrutniju sudbinu doživio je 1940, kad su Veležova vrata bila zapečaćena, a to se desilo poslije utakimce sa podgoričkom “Crnom Gorom”, igrane na godišnjicu napada Njemačke na Poljsku, nakon čega su uslijedile demonstracije i uzvikivanje parola poput “Dolje fašizam!”
U martu 1945. Velež je, poslije gotovo petogodišnjeg prislinog mirovanja, obnovljen, a najprije se takmičio u Oblasno-podsaveznoj, zatim Republičkoj, Trećoj i Drugoj ligi, da bi napokon 1952. postao član Prve savezne lige.
Premijera u toj eliti igrana je u Mostaru protiv Crvene zvezde, a u tom timu Veleža bili su Žarko Barbarić, Mensud Dilberović, Dane Prajo, Anton Bolfek, Hamdija Ćemalović, Vlado Slišković, Muhamed Mujić, Hasan Momić, Haldun Leo Hrvić i Slavko Hudarin.
Velež se u prvoligaše vratio u sezoni 1955/56. i ostaje u ovoj konkurenciji sve do raspada Jugoslavije, i igrao je sve do takmičarske 1991/92. da bi ratom 1992. okončao takmičenje.
Najveće uspjehe u prvenstvu države ostvario je u sezonama 1972/73, 1973/74. i 1987/88, kad je na kraju sezone osvajao drugo mjesto, a titula prvaka bila mu je najbliža 1973/74, ali od nje ga je odvojila samo gol-razlika, a na kraju jesenjeg dijela prvenstva 1987/88. bio je na prvom mjestu.
U Veležu je stasao veliki broj državnih reprezentativaca, članova svih selekcija, a u državnoj reprezentaciji igrali su: Enver Marić, Boro Primorac, Džemal Hadžiabdić, Blaž Slišković, Vladimir Matijević, Ivica Barbarić, Sead Kajtaz, Muhamed Mujić, Duško Bajević, Franjo Vladić, Vahid Halihodžić, Predrag Jurić, Semir Tuce i Meho Kodro.
Velež je četiri puta bio finalist Kupa Jugoslavije, dva puta su osvojili veliki srebreni trofej što je i najveći uspjeh jednog bosanskohercegovačkog tima u tom takmičenju.
Do prvog su stigli 1981., kad su sa trenerom Miloša Milutinovića trofej izborili: Enver Marić (kapiten), Avdo Kalajdžić, Aleksandar Micić, Dubravko Ledić, Vladimir Matijević, Veselin Đurasović, Dragan Okuka, Blaž Slišković, Vahid Halilhodžić, Adnan Međedović, Vladimir Skočajić i rezerve Momčilo Vukoje i Mirsad Mulahasanović.
U finalu je pobijeđen sarajevski Željezničar rezultatom 3:2, a trebalo je proći pet godina da “veležovci” po drugi osvoje Kup 1986. godine u sastavu: Vukašin Petranović, Draženko Prskalo, Goran Jurić, Nenad Bijedić, Vladimir Matijević (kapiten), Ismet Šišić, Sead Kajtaz, Vladimir Skočajić, Predrag Jurić, Anel Karabeg, Vladimir Gudelj i Semir Tuce, dok je njihov trener bio Duško Bajević, a u finalu je savladan Dinamo Zagreb sa 3:1.
Velež je prvi put bio finalist kupa 1958, a akteri toga događaja bili su Zdravko Brkljačić, Mensud Dilberović, Meho Handžić, Zdravko Rodin, Nikola Benco, Kruno Radiljević (kapiten), Milan Maksimović, Franjo Džidić, Omer Oručević, Šefik Alajbegović i Milorad Lazović, a tada je ekipu vodio Radomir Čabrić, protivnik je bila Crvena zvezda, i rezultat je bio 0:4 za Crvenu zvezdu.
Posljednje učešće Veleža u kupu bilo je 1989, igrali su: Petranović, Mili Hadžiabdić, Ismet Šišić (Ahmed Gosto), Ivica Barbarić, Veselin Đurasović, Ibro Rahimić, Zijad Repak, Zdenko Jedvaj (Damir Čerkić), Predrag Jurić, Anel Karabeg i Semir Tuce (kapiten), a predvodio ih je Žarko Barbarić. Protivnik je bio beogradski Partizan, a rezultat 6:1.
Velež je šest puta izlazio na evropsku scenu: 4 puta u Kupu UEFA i 2 puta u Kupu pobjednika kupova.
Najuspješnije su učestvovali od jeseni 1974. do proljeća 1975. kad su stigli do četvrtfinala Kupa UEFA.
Dotad su eliminirali moskovski Spartak, zatim bečki Rapid i engleski Derby County, da bi sa golom manjka (1:0, 0:2) izgubili u holandskom gradu Enschedeu protiv Twentea.
Dres Veleža nosili su: Slobodan Mrgan, Miomir Meter, Džemal Hadžiabdić, Marko Colić, Boro Primorac, Vladimir Pecelj, Jadranko Topić, Vahid Halilhodžić, Duško Bajević, Franjo Vladić, Momčilo Vukoje, Slavko Njeguš, Mirsad Mulahasanović, Dubravko Ledić, Marijan Kvesić, Milidrag Hodžić, Dragan Okuka i Ahmed Glavović sa trenerom Sulejmanom Repcom.
Godine 1988. Velež je stigao do 1/8 finala Kupa UEFA s trenerom Žarkom Barbarićem, iz te godine ostat će upamćen i veliki dvoboj sa njemačkom Borussijom Dortmund, kada je na prepunom “Bijelom brijegu”, pred više od 33.000 gledalaca, Velež slavio 2:1, ali rezultat iz Dortmunda glasio je 2:0 u korist Borussije.
Velež je bio finalist Srednjoevropskog kupa 1975. i pobjednik Balkanskog kupa 1981., a Učestvovao je i na Rapan kupu (1962. i 1963).
Mostarci su imali i nekoliko uspješnih turneja po inostranstvu, to su, prije svih, one po Srednjoj i Južnoj Americi i Dalekom istoku i Australiji.
Od 1965. do 1992. Mostar i Velež bili su domaćini najuglednijeg evropskog turnira u zimskom razdoblju.
Za to vrijeme na djelu je viđena 31 ekipa, među kojima i 16 stranih – 2 reprezentacije i 14 klubova.
Na stadionu pod Bijelim brijegom na toj reviji učestvovali su timovi iz Austrije, Mađarske, Čehoslovačke, Rumunije, Njemačke, Švicarske, Poljske, Irana, SSSR-a, kao i s prostora bivše Jugoslavije, izuzev iz Makedonije, a Mostarci su na svom tradicionalnom turniru bili prvi čak 15 puta.
Godine 1989. u četvrtom pokušaju (finalisti i 1969, 1977, 1987) i juniori Veleža osvojili su Omladinski kup Jugoslavije, i trofej se našao u rukama Nenada Džidića (kapiten), Siniše Spaića, Slavena Muse, Zvonimira Matkovića, Dražena Madunovića, Sanjina Pintula, Nikole Jokišića, Asmira Džafića, Nikole Juričića, Damira Vučića (Marina Pušića) i Darmina Begića, dok je njihov trener bio Salem Halilhodžić.
Od osamostaljenja BiH kao nezavisne države, Velež je uglavnom igrao u najjačem rangu nogometnog takmičenja, ali bez većih rezultatskih dostignuća, uz podatak da je dva puta ispadao i u niži rang takmičenja, da bi u sezoni 2020./21. klub osvojio treće mjesto i izborio nastup na evropskoj sceni, koji Mostarcima sada predstoji nakon pune 33 godine apstinencije.
