Prvu Upravu novooformljenog kluba činili su Anđelko Vlaho, Ranko Slijepčević, Borivoje Janjoš, Ljubomir Basta, Rudolf Beltram, Mihajlo Cvetković, Milan Pavić i Bogdan Tepšić. Prvi kapiten bio je Lazar Radić.
Osim ideje o osnutku radničkog kluba, postojala je i dilema o njegovu imenu. Radnički, Napredak, Sloga, Jedinstvo, Borac, Hercegovac, Iskra, Zvijezda bili su samo neki od prijedloga, ali je na kraju odlučeno da klub ponese originalno ime, one koje neće radničku ideju odati pred policijom, odnosno ime koje će u punom značenju označavati nešto što pripada Mostaru i Hercegovini.
Tako je na prijedlog Anđelka Vlahe klub dobio ime Velež, po planini iznad Mostara.
Zbog neimaštine Velež je u prvim godinama igrao u dresovima crne i bijele boje, a prvi dresovi crvene boje u Mostar su doneseni iz Zagreba. Donio ih je član Uprave kluba Vaso Pucarić.
Klub je egzistirao sve do pred sam Drugi svjetski rat kada je za kratko ugašen. Nakon rata rad kluba je obnovljen, a bilo je to u februaru 1945. godine. Osnivačka Skupština održana je na današnjem trgu Musala.
Prva utakmica obnovljenog Veleža odigrana je 13.marta 1945.godine, a protivnik je bila sportska sekcija Pozorišta narodnog oslobođenja Hercegovine. Sedam godina kasnije, tačnije u augustu 1952. godine Velež je po prvi put u svojoj historiji postao prvoligaš. Na starom Veležovom igralištu odigran je prvi prvoligaški meč, a protivnik Rođenih bila je beogradska Crvena Zvezda.
Mostarci su kroz historiju četiri puta dospijevali u finale Kupa Maršala Tita, čiji su veliki pehar podizali dva puta. Prvo je to učinila generacija Blaža Sliškovića i Vahida Halilhodžića 1981. godine, te kasnije generacija Semira Tucea i Seada Kajtaza 1986. godine.
Rad Veleža po drugi put zasutavio je rat 1992. godine. Agresija na Bosnu i Hercegovinu Veležu je odnijela gotovo sve.
Klub je prognan sa svog stadiona Pod Bijelim brijegom, pa u novijoj historiji svoje utakmice igra na stadionu u Vrapčićima. Prije 11 godina mostarski simbol je nakratko napustio društvo najboljih, ali se u Premijer ligu vratio nakon tri godine izbivanja. Uspjesi u poslijeratnoj historiji nisu zabilježeni.
