Kamennými hradbami byl Vyškov obehnán patrně ve 14. století. O jejich existenci v tomto období svědčí městská pečeť z roku 1403, kde byla znázorněna hradební zeď s věží a otevřenou bránou. V roce 1423 město dobyli a zcela zpustošili husité. Po husitských válkách bylo městské opevnění obnoveno, což dokládají písemné zprávy z té doby. Nejvíce zabezpečena byla východní strana města, kde hradba probíhala ve dvojité linii.
Přístup do města zabezpečovaly tři brány ze tří hlavních směrů: z Brna, Kroměříže a z Olomouce, které však byly zbořeny v průběhu 19. století. Pozůstatky městského opevnění se nacházejí za kostelem Nanebevzetí Panny Marie a v Pivovarská ulici. Výška hradeb dosahuje tři, někdy i šest metrů, síla zdiva je zhruba 155 centimetrů.[2]