Miestą prekybiniame kelyje, jungiančiame Vakarų ir Šiaurės Europą su Juodąja jūra, 1580 m. įkūrė ATR etmonas Janas Zamoiskis. XVI–XVII a. miestas klestėjo, o Zamostės tvirtovė buvo viena įspūdingiausių to meto ATR: miestą juosė galingų bastionų, kurtinų ir gynybinių griovių sistema, išnaudojanti Labunkos ir Topornicos upių ir pelkėtų slėnių teikiamus gamtinius pranašumus. Tvirtovė statyta tikintis galimų totorių antpuolių.