Na inicijativu grupe građana, mahom radnika i đaka Učiteljske škole, u Mostaru je 26. juna 1922. godine osnovan fudbalski klub Velež, i to sa predznakom RŠK (radnički šport klub). Ime je, nakon nekoliko prijedloga (Radnici, Napredak, Sloga, Jedinstvo,...) dobio po obližnjoj planini.
Prvi predsjednik Veleža bio je Anđelko Vlaho, a nakon što su tadašnje vlasti, nakon dva mjeseca provjeravanja „podobnosti“ članova uprave, odobrile rad kluba, krenulo se sa odigravanjem prvih utakmica, a rivali su bile mahalske ekipe. Nakon sticanja iskustva, ukrstila su se koplja i sa mjesnim rivalima (JSK- Jugoslovenski sportski klub; HŠK Zrinjski i SK Vardar), i većinom su te utakmice završavale visokim porazima.
U dvadesetim i tridesetim godinama prošlog vijeka kalio se tim, koji je igrao po regionalnim ligama, i većinom sa protivnicima iz regije. S iskustvom su došle i prve pobjede, a Velež je bio rado viđen gost, pogotovo kada su radnički klubovi u pitanju.
Upravo zbog toga, tadašnjoj vlasti je smetao rad kluba, pa su igrači i simpatizeri bili pod stalnom torturom policije, a vrhunac je stigao 1940. godine, kada je zabranjen rad kluba.
Naime, 1. septembra 1940. u Mostaru su prijateljsku utakmicu odigrali Velež i podgorička Crna Gora, a poslije utakmice, fudbaleri oba tima, zajedno sa svim prisutnim na utakmici, krenuli su ulicama Mostara demonstrirajući protiv tadašnjeg režima. Tada je policija na demonstracije odgovorila oružjem, pala je i prva krv, a dva dana kasnije službeno je zabranjen rad FK Velež.
I pored toga, u ilegali je djelovao FK Velež, a 22. decembra 1940. odigrana je i posljednja utakmica pred rat, i to protiv također zabranjenog Splita, u ovom gradu na jadranskoj obali.
Nakon toga uslijedio je Drugi svjetski rat, a gotovo svi članovi i simpatizeri crvenog kluba od prvog dana su se uključili u borbu protiv okupatora i njegovih domaćih pomagača, a kraj rata nije dočekalo njih 77.
Ipak, to nije pokolebalo 'rođene', koji odmah po završetku rata, obnavljaju rad kluba i kreću sa takmičenjem. Naravno, krenulo se iz Republičke lige, a već 1952. po prvi put Velež je član Prve savezne lige Jugoslavije, a nakon što se u sezoni 1955/56 osiguralo po drugi put mjesto u eliti, do raspadanja Jugoslavije Velež je bio član društva najboljih.
“Jasno da je najupečatljiviji period 'Veleža' onaj između ranih 1970-ih i kasnih 1980-ih. U tom periodu 'Velež' je izrastao u dobro organiziran, uspješan klub koji je imao kontinuitet rada. Ja stalno ističem i tu generaciju iz 1950-ih, koja je prva osigurala plasman u Prvu ligu, kao klub iz daleko najmanje sredine u odnosu na sve ostale. S druge strane, 'Velež' je teško stradao u dva rata. U Drugom svjetskom ratu je ostao doslovno bez svega, zabranjen mu je rad, a 77 njegovih igrača i članova kluba je poginulo ili ubijeno. U Agresiji na BiH 'Velež' je opet ostao bez svega, izbačen na ulicu, namijenjeno mu je gašenje, ali se digao iz pepela i radio u jako teškim uvjetima. Opet, i pored svih nedaća, mislim da 'Veležovi' navijači trebaju biti ponosni i na te periode svoje historije. Činjenicama poput one da je jedan od osnivača kluba Savo Medan bio sudionik ZAVNOBiH-a ili da je 'Velež' jedan od pokretača NSBiH i sudionik onog ratnog prvenstva u malom nogometu”, rekao je u izjavi za Stav Saša Ibrulj 2022. godine povodom promocije njegove knjige “Velež: priča o 100 godina mostarskih Rođenih”.
Kada je 1996. godine održana prva poslijeratna Skupština FK Velež na kojoj je za predsjednika kluba izabran Sead Balalić, on je tada rekao: „Mostar je ostao bez svojih simbola, dušmani nam porušiše Stari most, ali nisu uspjeli ubiti Velež. Velež će i dalje predstavljati grad na Neretvi u zemlji, ali i u svijetu."
Saša Ibrulj smatra da ljudi vole Velež zbog činjenice da je vjeran svom identitetu i filozofiji, bez obzira na loše i dobre dane kroz koje prolazi. Velež je klub koji je iznad rezultata, iznad sporta, i to ljudi poštuju.