A felsővárosiak kápolnáját, már 1775-ben templomnak minősítették. A Belvárosi és a Felsővárosi plébánia, közel azonos létszámmal vált külön: a felsővárosiak első plébánosa Szabó József lett 1778-ban. A városrész polgárai a bővítés érdekében folyamatosan kulcsoltak a városvezetésnél és a püspökségnél. Gyűjtést is szerveztek a templom megnagyobbítására 1800-ban szép számmal adakoztak a városrész lakói.
A felsővárosi gazdák 1807-ben felajánlották, hogy a Szent Sebestyén templom melletti romos iskolát megveszik és lebontják a tűzveszély miatt illetve nem utolsó sorban a templom „díszességét” is növelni akarták. Az élelmes hívők a bontási anyagot elárverezték és 1070 forintért eladták, majd ezt a templom javára felajánlották. A templom előtti utat 1809-ben pedig lekövezték, az összegyűjtött pénzből.
A két torony építése 1836-ban történt, Fridl Károly rajzmester tervei alapján. Az építkezés idejére még a téglaégetőt is a templom rendelkezésére bocsátotta a város. A követ a Csúcsos-hegyi kőbányából hordták, az építkezést pedig Vass János tanácsos vezette. Az építkezés azonban nem úgy sikerült ahogyan azt elképzelték, ugyanis a templomtornyok már 1840-ben megrepedeztek, ezt 1849-ben Szász Ferenc építőmester szakértői véleményben közölte a tanácsüléssel, hogy a Szent Sebestyén templom tornyait meg kell erősíteni, az azt építő Langmár Mihály kőműves mester úrnak. Ezeket azonban a tanács javíttatta meg és a költségeket behajtatta a kőművesen. A kőfaragó munkájáért, pedig még az építkezés után két évvel mindig tartoztak a mester özvegyének. A toronyórát pedig Németh Ignác órásmester hat évi jótállással 1000 forintért készítette, ezt is adományokból fizették.
A templomban egészen 1885-ig tartottak német nyelvű istentiszteletet, ugyanis ebben az esztendőben a megyéspüspök határozatban szüntette meg a felsővárosi plébánián és a ciszterciták templomában a német nyelvű liturgiát és intézkedett a magyar nyelvű istentisztelet meghonosításáról.
A felsővárosi templomnak 1917előtt hat harangja volt, amik ekkor vándorútra keltek és beolvasztották őket ágyúnak, harang újra csak 1927-ben lett, az akkori újság beszámolója szerint április 14-én „megkondult a felsővárosi Szent Imre harang. A 951 kg-os harangot Walser Ferenc budapesti cégének harmadszori öntése. A templomban már a harmincas évek elején volt villanyáram és kivilágítottak voltak a toronyórák, azonban a város akkoriban nem fizette a villany költségeit így azt kikapcsolták, pedig a felsővárosi templom toronyórái kivilágítására szolgáló 6 darab 60 wattos átalányégő este is láthatóvá tette az órákat.
A templom a II. Világháborúban megsérült, egyik tornyát el is vesztette és csak 1960-ra épültek fel teljesen a tornyok a hívek adományából, továbbá ekkorra restaurálták a Szent Sebestyén szobrot is.
