Боје клуба су црвене кад игра као домаћин и беле кад гостује, а на грбу је од оснивања црвена петокрака, с изузетком раздобља 1992—2005. Због велике љубави Мостараца према клубу, дали су му надимак "Рођени", који и данас носи. Навијачка група клуба зове се „Ред Арми Мостар”.
Фудбалски клуб Вележ основан је као Раднички шпортски клуб (хрв.RŠD/RSD — Радничко спортско друштво, РСД)26. јуна1922. године, по одлуци мостарске партијске радне организације, после Обзнане, по којој власти затварају Раднички дом у Мостару, забрањују синдикате и све организације које носе радничко име или су напредних идеја. Оснивачи су бирани међу некомпромитованим људима. Спретно стилизована правила су убрзо одобрена. Главни иницијатор међу оснивачима био је Гојко Вуковић, члан КП, а у управу су изабрани истакнутији партијски руководиоци: Ристо Самарџић-Ринда, (убијен у полицијском затвору у Загребу 1930) Угљеша Јањић, Саво Неимаровић и Гојко Божовић. Име је добио по планини Вележ, која се диже изнад Мостара.
Од 1925. клуб носи црвене дресове, а од 1926. и значке у облику петокраке звезде, у чијој је средини бела лопта с текстом "РШД Вележ Мостар".
Сваког четвртка после тренинга организован је идеолошко политички рад са играчима и симпатизерима, а предавачи су били истакнути партијски руководиоци. Због тога је клуб привремено забрањиван 1929, 1932. и 1934. а на основу петиција грађана поново добија дозволу за рад. На петицији 1934. године било је за то време велики број око 3000 потписа.
У почетку Вележ се трудио да окупи раднике и делује на њих а касније и на квалитет играча тако да је у сезони 1934/35 од 32 утакмице није изгубио ниједну. Добио је тридесет и одиграо две нерешене.
На годишњицу почетка Другог светског рата1. септембра1940. после утакмице Вележ - Црна Гора (Будућност) из Подгорице организоване су демонстрације и том приликом је рањено више демонстраната и деце, а око 50 је ухапшено (КПЈ, СКОЈ и симпатизери). Због тога је 2. септембра објављен генерални штрајк, а власти су 3. септембра забраниле рад синдиката, затвориле Раднички дом и забраниле рад Вележа.
Спортске трофеје склонио је Мешак Ћумурија, који је 1944. одведен у концентрациони логор и убијен, па су сви спортски трофеји Вележа загубљени.
Револуционарна традиција Вележа дошла је до изражаја у току НОБе када је већина играча и управе је активно учествовала у НОРу, од којих су многи и погинули.
После Другог светског рата
Вележ је обновљен у априлу1945. Фудбалска екипа се у почетку такмичила у републичкој лиги, 1950. у Трећој савезној лиги, 1951. у Другој савезној лиги, а затим у републичкој и кроз квалификације постаје члан Прве савезне лиге. Године 1953. поново се такмичи у нижем степену, да би такмичарске сезоне 1955/56 постао стални члан Прве савезне лиге, до распада СФРЈ1991. године. Иако никад није освојио титулу првака. Три пута је био други, а четири пута финалист Купа маршала Тита, од чега је два пута био освајач 1981. и 1986. године.
У том периоду Вележ је дао више репрезентативаца и фудбалских судија.
У Спортском друштву Вележ поред фудбалског клуба постојале су секције и клубови за атлетику, пливање, ватерполо, рукомет, кошарку, стони тенис, рвање и џудо. Фудбалски клуб Вележ је одликован Орденом братства и јединства са златним венцем.
Доласком рата Вележ остаје буквално без свега што је имао. После рата Мостар постаје подељен град, на два дела: источни и западни.
Обновом рада хрватских клубова, којима је рад био забрањен после 1945. за време Југославије, Вележ је изгубио стадион и велику играчку основу, што се одразило и на његове резултате у Фудбалском првенству Босне и Херцеговине. Од тог периода не представља онако снажни клуб, као што је некада био.
На источној страни града преовладавају навијачи Вележа, а на западној навијачи Зрињског. Утакмице између ова два тима су дербији најгледанији у Босни и Херцеговини, а због нетрпељивости навијача, која је и данас присутна, то су утакмице високог ризика.
Стадион
Вележ је током своје историје променио три домаћа стадиона: "Старо Вележово" на Авенији, затим Стадион под Бијелим бријегом, а од 1992. Вележ игра на стадиону у мостарском предграђу Врапчићима, који има капацитет 7.000 гледалаца.