Ова ужичка црква има дугу и богату историју. О њеном пореклу и години изградње постоји више верзија. Са становишта званичне историје, црква је подигнута 1828. године. Као главни аргумент за ову тврдњу служе забелешке аустријског путописца Феликса Каница. Каниц је приликом посете Ужицу 1860. године, забележио: “У најстаријој варошкој четврти посетио сам црквицу Св. Марка, која се са својим малим дрвеним звоником налазила у једној башти; она је освећена још 1828. па је 1888. обновљена, а 1889. за време рестаурације главне цркве, требало је да замени ову“. Каниц је тада направио први познати цртеж цркве Св. Марка.
Година 1828. се тако узима као званичан датум изградње цркве и тај датум се налази уписан на информационој табли поред улаза у цркву. Усмено предање говори другачије. По усменом предању, црква је подигнута много раније, још 1721. године. По овоме предању, најзаслужнији за подизање цркве био је шејх Мухамед, Ужичанин који је дао дозволу да се ова црква подигне. По предању, шејх Мухамед је због тога тешко настрадао – омрзнут од стране других Турака, смртно је страдао у сукобу са њима, нешто пре 1750. године.
Као што се често покаже, народна предања настају на основу неких стварних догађаја, па тако и у овом предању има нешто истине. Због ратних сукоба између Аустрије и Турске, велики део српског народа је пребегао у Аустрију, па су многи делови Србије остали празни и напуштени. Турци су из економских разлога желели да се становништво врати, па су били спремни и на неке уступке. Тако је и шејх Мухамед одобрио Србима из Ужица да се себи подигну малу цркву. Ово усмено предање потврђено је и у неким документима. Ово предање се у писаној форми први пут помиње у делу „Самоуки рукопис“, аутора ужичког пекара Миладина Радовића са Татинца. Он 1911. године пише о дешавањима у ужичком крају којима је био очевидац или је слушао о њима од својих старих. Радовић пише: „Тај је шеик одобрио Србима да начине себи мало цркве, ђе ће се богу молити, и још неке олакшице, те су зато неки Турци, који су дрчини, омрзли на шеика.“ По Радовићу, Шејх Мухамед није ктитор цркве. Његова улога се сводила на давање дозволе за подизање цркве. Радовић не помиње конкретно 1721. годину као годину изградње цркве.
Други доказ указује на подизање цркве око 1721. године. То је антиминс који се чува у ризници цркве Св.Марка. Реч је о антиминсу који је освештао рашки митрополит Григорије ИИИ, који је на рашком трону био од 1697. до 1730. године. Антиминс је платно у коме је често ушивен део светитељских моштију и на коме се може служити литургија. Иако нема доказа да је овај антиминс урађен за ову цркву, његово постојање у ризници цркве Св. Марка указује на његову везу са црквом.
На основу свега, може се закључити да је прва црква подигута око 1721. године, по повратку већег броја Срба у Ужице и околину. 1737. године долази до новог Аустријско-Турског рата, када су због српске подршке Аустрији у том рату, многе цркве разрушене и спаљене. Вероватно је тада страдала ова првобитна црква, јер о њој више нема никаквих записа ни помињања, све до 1828. године. Тада је, највероватније, садашња црква подигнута на темељима те старе, срушене цркве посвећене Светом апостолу Марку.
Током година црква је више пута обнављана. Током обнове у периоду 1885-1890 година, уз цркву је подигнут звоник од дрвета, висине 22 м. Звоник је подигао Ристо Тешић, ужички сајџија, а ктитори су му биле ужичке занатлије. Ристо Тешић је био веома значајна личност у прошлости Ужица. Поред тога што је са приљатељима обновио цркву, што је подигао дрвени звоник, он је уредио порту цркве, посадио липе у дворишту, оградио је и тако сачувао до данашњих дана. Липе које је Тешић посадио и данас су прави украс црквеног дворишта. Тешић је био и први еколог Ужица – он је творац ужичког Великог парка поред Ђетиње, и још неких паркова у граду.
И после ове велике обнове, било је још неколико обнова цркве – 1921, па 1966. и 1990. године. Црква и данас изгледа веома лепо, очувано и све је на свом месту. То су резултати последње обнове цркве у периоду од 2004. до 2006. године. Овом последњом обновом црква је сачувала стари изглед и добила нови сјај. Црква је добила подно грејање, урађен је нови иконостас од ораховог дрвета, рад Љубана Марића из Лелића. Иконе на иконостасу дело су академског сликара мр. Видоја Туцовића, професора новосадске академије на одсеку за зидно сликарство.
Посебну вредност у овој цркви представља ризница са великим бројем старих и вредних предмета. У цркви се налази збирка гравура насталих од 17. до 19. века, као и предмети примењене уметности, радови ужичких кујунџија. Лепо је уређено двориште цркве. Ужичани имају где да седну, да се одморе и да уживају, како у лепоти старе цркве, тако и у дворишту препуном зеленила и цвећа.