
V prostorách kostela sv. Mikuláše a blízkém okolí stával menší hrad. Tehdy byl využit zdejší vyvýšený pahorek nad dnešním mlýnským náhonem, který přitéká z Litovelského Pomoraví. Pravděpodobně se jednalo o malé šlechtické sídlo, možná na základech bývalého kostelíka, či byl se stavbou nějak propojen. Údajně měl totiž kostelík v Horce stávat již v dávné minulosti. Místo bylo jistě vybráno dobře, protože v záplavové části řeky Moravy tehdy bývaly četné bažiny a mokřady, které sídlo jistě výborně opevňovaly. Místo připomíná nedaleké Náklo, kde stával též menší hrádek a dnes zde stojí opevněný kostel. Již r. 1250 je zmínka o jistém Pardusovi z Horky a o Horeckém mlýně. Ves se připomíná r. 1250 a zdejší hrad r. 1406. Že stál zcela jistě v prostorách dnešního kostela a jeho okolí připomíná dodnes používaný název Podhradí, který nese i ulička pod kostelem. Jméno nesou i místní názvy polností severně nad obcí - Podhrady a Přední Podhrady, či Podhradský rybník na Mlýnském potoce. Hrad byl spolu s kostelíkem za husitských válek značně poškozen.
K r. 1520 víme o majiteli Horky Petrovi, který měl pět synů. V r. 1535 byla Horka prodána městu Olomouci. Z písemnosti též víme, že r. 1593 byl již hrad rozbořen. Samotný kostel sv. Mikuláše se datuje k r. 1753.