Historija fudbalskog kluba Velež počinje 26. juna 1922.
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 športskog društva koje bi kako okupljalo radnike i druge ljubitelje fudbala 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 športskog 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.
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. U dresovima crvene boje fudbaleri Veleža zaigrali su tek 1925. godine, a 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. 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. Godine 1924. bio je finalist olimpijskog turnira u Mostaru. Već u sezoni 1934/35. ubrajao se među kvalitetnije bosanskohercegovačke klubove. Veležu je privremeno zabranjivan rad. Još okrutniju sudbinu doživio je 1940, kad su Veležova vrata bila zapečaćena. 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. 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. 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. Titula prvaka bila mu je najbliža 1973/74, ali od nje ga je odvojila samo gol-razlika. Na kraju jesenjeg dijela prvenstva 1987/88. bio je na prvom mjestu.
Ostat će upamćen i veliki dvoboj sa slavnom Borussijom Dortmund. Na prepunom Bijelom brijegu, pred više od 33.000 gledalaca, Velež je 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. Učestvovao je i na Rapan kupu (1962. i 1963). Rođeni su imali i nekoliko uspješnih turneja po inozemstvu. 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. Rođeni su na svom tradicionalnom turniru bili prvi čak 15 puta.
Nogometna škola
Godine 1989. u četvrtom pokušaju (finalisti i 1969, 1977, 1987) i juniori Veleža osvojili su Omladinski kup Jugoslavije. Pobjednički trofej bio je 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, a njihov trener bio je Salem Halilhodžić.
