Vznik fotbalového klub je těsně spojený s 5. brigádou Pohraniční stráže, jejíž velitelství se od roku 1951 nacházelo v Chebu. Vznikl tak ve stejném roce pod názvem Vojenská sokolská jednota Sokolovo. Už o rok později byl zahrnut do struktury sportovních oddílů ministerstva vnitra, nesoucích jednotný název Rudá hvězda; pouze v letech 1966 až 1972, kdy Pohraniční stráž spadala pod ministerstvo obrany, se jmenoval VTJ Dukla Hraničář. V roce 1990 došlo k přejmenování na Sportovní klub policie Union, pro fanoušky však stále zůstal „Hvězdou“. Finanční příspěvek ministerstva postupně klesal a po sametové revoluci spadá klub do rukou soukromých investorů. Klub se po několika sezónách ocitá v těžké finanční situaci, která vyvrcholila konkursem v roce 1996. Důsledkem konkursu byl zánik A-mužstva, s čímž souviselo i neudělení licence potřebné k další účasti v lize. Klub strávil v nejvyšší československé soutěži šestnáct sezón. Kontinuitu se podařilo zachovat díky sekci mládeže, jež se spojila s Lokomotivou Cheb do nového subjektu SK Cheb. Po roční přestávce bylo obnoveno i mužstvo dospělých, které působilo v krajském přeboru.
V roce 2001 můžeme mluvit o znovuzrození klubu, který navazuje na tradici chebského fotbalu a ligovou éru Rudé hvězdy Cheb pod názvem FC Union Cheb 2001. Po dvou sezónách klub postoupil do divize, odkud v sezóně 2005/06 postoupil do ČFL, díky odřeknutí účasti v této soutěži od Blšan, i z nepostupového 2. místa. V ČFL se v sezóně 2006/07 umístil ve středu tabulky na 9. místě, v další sezóně však přišel výkonnostní propad a také neochota sponzorů, takže i přes 15. místo zaručující setrvání v soutěži Union nemohl zůstat v této lize, své místo poskytl FC Písek a vzdal se i místa v divizi, nastoupil poté do krajského přeboru.
V roce 2011 je přejmenován klub na nynější název FK Hvězda Cheb. V sezóně 2012/2013 se Hvězdě opět podaří postoupit do divize, kde setrvala pouze dvě sezóny. Návrat do divize se uskutečnil v sezóně 2019/20 a Hvězda v této soutěži nadále setrvává.
Začátkem roku 2018 přibývá také plavecký oddíl, který vychovává mládež věnující se plaveckým sportům. Od sezóny 2021/22 se kategorie mladších žáků, starších žáků a mladšího dorostu staly členy Svazu futsalu a zimní přestávku mládež vyplňuje krajským přeborem ve futsalu.
V sezóně 2021/22 došlo k zásadní změně ve vedení klubu, který opustilo kompletní vedení. Sportovní ředitel Mgr. Václav Sýkora byl pověřen předložením návrhu nového výboru a sestavil tým, který byl následně zvolen valnou hromadou. Předsedou se stal hráč Tomáš Bauer, funkci místopředsedy vykonává Mgr. Václav Sýkora a dalšími členy jsou vedoucí žákovských družstev Zuzana Honzejková, sekretář klubu a garant činnosti mládeže Vítězslav Janda, hráč Jakub Klepáček a trenér mužů Miroslav Šebesta. Nově zvolený tým lidí spjatých s Hvězdou jistě dá klubu nový impuls, prosadí dokončení rekonstrukce stadionu a naváže na slavnější období Hvězdy...
V roce 2021 si Cheb připomněl sedmdesáté výročí od vzniku nejvýznamnějšího chebského fotbalového klubu, jehož tradici drží FK Hvězda Cheb. Klub navazující na slavnou historii provázenou vzestupy i pády se v současné době věnuje nejen dospělému fotbalu, ale zejména výchově mládeže. Jeho cílem je rozvíjet mládežnickou základnu a vychovávat vlastní hráče pro mužské soutěže. A-tým mužů pokračuje v divizi jako čtvrté nejvyšší soutěži, rezerva hraje 1.A třídu. Ve Hvězdě trénuje devět mládežnických kategorií - dorost, který v sezóně 2020-2021 obsadil první místo krajského přeboru, starší žáci, dvě mužstva mladších žáků, čtyři mužstva přípravkových kategorií a elévové jakožto fotbalová školička. Právě tato masa mládí je perspektivou dalšího rozvoje a věříme, že o našich nadějích ještě hodně uslyšíme.
