Poljana pored Sjevernog logora je 26. lipnja 1922. bila mjestom osnivanja još jednog u nizu nogometnih klubova u Mostaru. U gradu su već tada djelovali Zrinjski, JŠK i Vardar, a postojalo je i još nekoliko mahalskih ekipa poput Luke, Brankovca ili Carine. Osnivači novog kluba se nikako nisu mogli odlučiti za ime, a među prijedlozima su bili Radnici, Napredak, Sloga, Jedinstvo, Hercegovac, Borac, Sloboda, Hum, Hercegovina...
Na kraju je jednoglasno usvojeno ime Radnički športski klub Velež, a u povijesti će ostati zapisana imena njegovih osnivača: Anđelko Vlaho – predsjednik, Ranko Slijepčević – potpredsjednik, Borivoje Janjoš – prvi tajnik, Ljubomir Basta – drugi tajnik, Rudolf Beltram – blagajnik.
Prve utakmice
Svoje prve utakmice Velež je igrao protiv ostalih mostarskih klubova i mahalskih ekipa, a momčad su tada činili Marko Vučijak, Ljubo Zrimšek, Savo Turanjanin, Mile Pavić, Lazar Radić, Milan Rajković, Bogdan Tepčić, Ranko Slijepčević, Branko Turanjanin, Savo Medan, a kasnije se pridružuju i Mustafa Pašić, Salko Manjgo, Ante Strazičić, Ljubo Sudar, Milan Trbulin, Vuko Čulajević, Desko Jelić, Stanko Janjić, Ragib Hebib, Salko Hadžiomerović, Hasan Ćišić, Miko Kahmi, Rudolf Beltram, Armin Altarac...
Uskoro počinju i gostovanja, pa tako Velež nastupa u Dubrovniku, Livnu, Splitu i Sarajevu, a sudjeluje i na humanitarnim turnirima poput onoga iz 1926. organiziranom za pomoć obiteljima poginulih rudara mostarskog rudnika uglja.
Velež je igrao utakmice sve do 1940. godine kada mu se zabranjuje rad. Svoju posljednju utakmicu prije zabrane Velež je protiv podgoričke Crne Gore, i to u sastavu: Boro Ćećez, Safet Džinović, Mile Barbarez, Fadil Buturović, Remzija Duranović, Muhamed Hadžiomerović, Savo Milović, Šefkija Ćemal, Hilmija Trebović, Haldun Hrvić i Sulejman Gušanac.
Obnova rada
Nakon II. svjetskog rata, Velež obnavlja svoje djelovanje, a prve utakmice igra u kvalifikacijama za Prvu saveznu ligu 1946. protiv banjalučkog Borca, tuzlanske Slobode, zeničkog Čelika i sarajevskog Torpeda, ali se ne uspijeva plasirati. Tek 1952. Velež se uspijeva plasirati u Prvu ligu, ali iz nje ispada na kraju sezone. Povratak u najelitnije jugoslavensko nogometno natjecanje se nije trebao dugo čekati, jer se Velež u Prvu ligu plasira već iduće godine.
Na međunarodnoj sceni
Svoje prvu međunarodnu utakmicu, Velež je odigrao 1948. 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.
Svoj najveći uspjeh u europskim natjecanjima Velež postiže u sezoni 1974/75. kada dolazi do četvrtfinala kupa UEFA izbacivši pritom moskovski Spartak, bečki Rapid i Derby County. U četvrtfinalu Velež ispada od nizozemskog Twentea unatoč domaćoj pobjedi od 1:0. Velež je još dva puta nastupao u kupu UEFA, a posebno se pamti domaća pobjeda protiv Borussie iz Dortmunda 1987.
Februarski turnir
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. Iako nikad nije osvojio jugoslavensko prvenstvo, Velež je nekoliko puta igrao u finalu Kupa.
Kup Maršala Tita
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ć.
Reprezentativci
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ć.
Iako svoju seniorsku karijeru nisu ostvarili u Mostaru, bivši reprezentativci BiH Sergej Barbarez i Hasan Salihamidžić su nastupali u omladinskom pogonu Veleža.
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.