Radnički športski klub Velež je osnovan 26. lipnja 1922. godine u Mostaru. Na inicijativu radnika i đaka Učiteljske škole zakazan je osnivački sastanak u blizini Sjevernog logora u Mostaru.
Nakon čitanja pravila kluba, izabrana je i uprava koju su činili: Anđelko Vlaho (predsjednik), Ranko Slijepčević, Borivoje Janjoš, Ljubomir Basta, Rudolf Beltram, Ljubo Zrimšek, Ljubo Pavić, Mihajlo Cvetković, Milan Pavić, Bogdan Tepčić i Lazar Radić.
Na toj osnivačkoj skupštini bilo je mnogo prijedloga o imenu kluba: Radnici, Napredak, Sloga, Jedinstvo, Hercegovac, Borac, Sloboda, Hum i Hercegovina, ali je na kraju ipak izabrano ime Velež.
Prvi dresovi Veleža su bili bijele boje, a šile su ih sestre Ranka Slijepčevića, Zorka i Radojka.
U početku je Velež igrao s mahalskim ekipama, te s lokalnim rivalima kao što su JŠK, HŠK Zrinjski i SK Vardar, a kasnije je igrao prijateljske utakmice u Dubrovniku, Makarskoj, Konjicu, Livnu i ostalim obližnjim mjestima.
Prvu utakmicu pod reflektorima, Velež je odigrao u svibnju 1937. na turniru povodom 15 godina osnivanja kluba. Pored Veleža, na turniru su sudjelovali i Hajduk iz Sarajeva, Željezara Zenica, Jugoslavija iz Čapljine, te mostarski klubovi JŠK, Vardar, MOSK i Jedinstvo.
Posljednju utakmicu prije zabrane djelovanja 1940., Velež je odigrao s podgoričkim klubom Crna Gora.
Nakon završetka II. svjetskog rata, Velež obnavlja djelovanje i spaja se s OFK Snaga iz Mostara.
U SFRJ, Velež je nekoliko godina pokušavao izboriti mjesto u prvoligaškom natjecanju. Šest godina nakon osnivanja savezne lige, Velež se plasirao u najelitniji rang. Prvu prvoligašku utakmicu Velež je odigrao u Mostaru s beogradskom Crvenom Zvezdom. Za Velež su tada nastupili: Barbarić, Dilberović, Prajo, Borozan, Bolfek, Ćemalović, Slišković, Mujić, Momić, Hrvić i Hudarin. Velež je izgubio rezultatom 0:1.
Iako nikad nije osvojio jugoslavensko prvenstvo, Velež je nekoliko puta igrao u finalu Kupa. Velež je prvi put finale odigrao protiv Crvene zvezde i izgubio rezultatom 4:0. U svom drugom finalu, Velež je imao više sreće. Pod vodstvom trenera Miloša Milutinovića, koji je kasnije vodio i Partizan, Bešiktaš, Altay i jugoslavensku reprezentaciju, Velež je u Beogradu pobijedio sarajevski Željezničar rezultatom 3:2. Golove za Velež su postigli Vahid Halilhodžić (2) i Dragan Okuka.
Svoj drugi jugoslavenski kup, Velež je osvojio 1986. godine u Beogradu pobjedom nad zagrebačkim Dinamom rezultatom 3:1. Golove za Velež su postigli Nenad Bijedić (2) i Predrag Jurić.
Već od 1948. godine, Velež sudjeluje u prijateljskim utakmicama na međunarodnoj sceni. Prvu utakmicu je odigrao u kolovozu 1948. u Mostaru protiv reprezentacije čehoslovačkog grada Brna. Od tada, Velež je igrao brojne prijateljske utakmice kod kuće, ali i na turnejama u Turskoj, SAD-u, Libiji, Australiji, Maleziji, Južnoj Koreji, Hong Kongu, te Srednjoj i Južnoj Americi (Kostarika i Peru). Na ovim turnirima, Velež je, osim s klubovima, igrao i protiv državnih reprezentacija, kao što su SSSR, Čehoslovačka, Južna Koreja i Poljska.
Jedna od najdojmljivijih prijateljskih utakmica je svakako gostovanje tadašnjeg engleskog prvoligaša West Bromwich Albiona u Mostaru 11. svibnja 1972. povodom puštanja u rad reflektora na stadionu „Pod Bijelim Brijegom“, koju je Velež izgubio rezultatom 2:3.
Srednjoeuropski kup je natjecanje u kojem je Velež igrao 1960. i 1975. kada je u finalu izgubio od austrijskog Wackera. Dotad su Rođeni igrali s talijanskim klubovima Alessandria i Perugia, te Austrijom iz Beča.
Velež je 1980. osvojio Balkanski kup, pobijedivši Trakiju iz Plovdiva, Flamurtari iz Valone i AEK iz Atene.
U preteči Inter-toto kupa, Rapan-Inter kupu, Velež je nastupio 1962. godine. Iako su dva puta pobijedili njemački Hindelheim, pobijedili i remizirali s nizozemskim Blauwitom, Veležovci su i dva puta izgubili od mađarskog kluba Pecs, te su se oprostili od natjecanja.
Iduće godine, Velež je također nastupao u ovome kupu igrajući u skupini protiv čehoslovačke Slovnafte, poljske Zaglebie i istočnonjemačkog Motora iz Jene. Velež je bio drugoplasirani u toj grupi.
U Kupu UEFA, Velež je prvi put nastupio 1972. godine, ali je ispao već u prvom kolu kupa UEFA-e od rumunjskog Tatrana.
Već iduće godine, Velež je došao do četvrtfinala kupa UEFA izbacivši na putu sovjetski Spartak iz Moskve, austrijski Rapid iz Beča i engleski Derby County. U četvrtfinalu ga je izbacio nizozemski Twente Enchede, unatoč Veležovoj pobjedi na domaćem terenu od 1:0. Twente je u uzvratu pobijedio s 2:0.
U četvrtfinalu kupa UEFA su igrali: Mrgan, Meter, Dž. Hadžiabdić, Ledić (Mulahasanović), Čolić, B. Primorac, Topić, Kvesić, Bajević, Vladić i Vukoje, dok su u uzvratu nastupe upisali još Prskalo i Halilhodžić.
Velež je treći put sudjelovao u kupu UEFA u sezoni 1986/87. Izbacio je švicarski Sion, ali je ispao od njemačke Borussije iz Dortmunda, unatoč domaćoj pobjedi od 2:1.
U sezoni 1989/90., Velež je uspio izbaciti ciparski Apoel i portugalski Belenenses, ali je ispao od škotskog Heartsa.
Dva puta osvojivši Kup Jugoslavije, Velež se plasirao i u Kup kupova. U oba nastupa, Velež je ispao u drugom kolu. U sezoni 1981/82., Velež je izbacio luksemburški La Jeunesse, a ispao je od istočnonjemačke Lokomotive iz Leipziga. Pet godina kasnije, Velež je u ovom natjecanju pobijedio mađarski Vašaš, ali je ispao od bugarske Vitoše. Utakmica protiv Vitoše je bila i posljednja službena utakmica Veleža u europskim natjecanjima.
Od 1965. godine, Mostar je bio domaćin Februarskom turniru koji se održavao do 1992. godine. Osim jugoslavenskih klubova, na turniru su sudjelovale i državne reprezentacije, te mađarski, istočnonjemački, austrijski, švicarski, sovjetski, iranski i drugi klubovi.
Posljednji Februarski turnir je održan 1992. godine, uz sudjelovanje tuzlanske Slobode i banjalučkog Borca.
Iz Veleža je ponikao i velik broj jugoslavenskih reprezentativaca. Prvi među njima su bili Muhamed Mujić i Kruno Radiljević koji su nastupili na Olimpijskim igrama 1956. u Melbourneu. Nakon njih, nastupe u reprezentaciji je upisao velik broj Veležovih igrača, dok su čast igranja na Svjetskim prvenstvima imali Muhamed Mujić (1962. Čile), Dušan Bajević, Enver Marić i Franjo Vladić (1974. – SR Njemačka) i Vahid Halilhodžić (1982. – Španjolska).
Na Svjetskom prvenstvu 1998. u Francuskoj, na popisu reprezentativaca Hrvatske se našao i bivši igrač Veleža Goran Jurić.
Od stranih igrača u Veležu, zabilježen je jedino vratar Aleksej Prudnjikov, sovjetski olimpijski reprezentativac.koji je prethodno nastupao za moskovske klubove Dinamo i Spartak. U Veležu se nije naigrao, te je zabilježio samo dva nastupa.
Posljednju domaću utakmicu u jugoslavenskom prvenstvu, Velež je odigrao u ožujku 1992. protiv Zemuna.
Prisilnim gašenjem tijekom rata 1993. godine, Velež prestaje s radom, ali krajem iste godine se formira novo rukovodstvo, te se obnavlja rad kluba.
Nakon završetka rata, Velež sudjeluje u najvišem rangu natjecanja, s nekoliko godina u 1. ligi Federacije BiH.