Počátky fortu na Šibeničním vrchu jsou identické s fortem na Tabulovém vrchu. U zrodu pevnůstky stál inženýr Camillo Vacani, jehož projekty byly později (v letech 1838-1939) přepracovány pevnostními inženýry z místního fortifikačního ředitelství v Olomouci. Výstavba fortu vzdáleného 750 metrů od města pak probíhala mnohem komplikovaněji než v případě jeho dvojčete na Tabulovém vrchu. Již krátce po zahájení výstavby v roce 1839 se totiž ukázalo, že byl objekt založen na nevhodném místě. Jílovitá půda a nestabilní podloží značně komplikovaly každodenní práce více než 300 dělníků a současně způsobovaly značné škody na již vybudovaných částech objektu. Mnohé části fortu proto musely být opravovány a přestavovány, což způsobilo nejen výrazné navýšení rozpočtu (celkové náklady byly nakonec vyčísleny na 850 000 zlatých), ale i značné narušení původního harmonogramu výstavby. V důsledku těchto problémů byl Fort na Šibeničním vrchu dobudován až v roce 1851. Po svém dokončení byla pevnůstka využívána jako vojenské kasárny a ke skladovacím účelům. V dobách, kdy neprobíhala žádná vojenská cvičení nebo nebyla pevnost připravována na útok nepřítele, zde bylo ubytováno přibližně 500 vojáků. V roce 1866, v časech prusko-rakouské války, zde sloužilo 1150 mužů a fort byl osazen 24 děly. Po zrušení pevnostního statutu města v roce 1886 sloužil jako jezdecká škola nebo kasárna těžkého dělostřelectva. V letech 1919–1948 zde byly umístěny výrobní dílny závodu Letov. Od roku 1949 až do 90. let 20. století se tu nacházel vojenský Automobilový opravárenský závod. Dnes je fort v držení soukromého subjektu a část jeho objektů je nadále využívána k výrobním a skladovým účelům.