La struttura fu costruita nel piccolo villaggio di Novogorodok-na-Osetre tra il 1528 ed il 1531. Appena due anni dopo, il cremlino subì il primo attacco militare ad opera dei tartari di Crimea. Nel 1541 vi fu un nuovo attacco e la fortezza fu assediata dagli uomini guidati dal khanSahib I Giray che, però, furono sconfitti da Nazar Glebov. Ulteriori attacchi da parte dei tartari di Crimea si verificarono nel 1544, nel 1570, nel 1573 e nel 1591.[1]
Nel 1681 lo zarFëdor III autorizzò la ricostruzione della cattedrale di San Nicola al posto della fatiscente struttura precedente. Nel XVIII secolo Zarajsk e la sua fortezza persero il proprio ruolo militare strategico per via dell'apertura di nuove rotte commerciali. All'inizio del XX secolo le autorità decisero di ricostruire la cattedrale della Decollazione di San Giovanni Battista. Nel 1918 l'area del cremlino fu trasformata in un complesso museale. Durante la seconda guerra mondiale il territorio di Zarajsk fu occupato dai tedeschi, ma il cremlino non subì danni.
Dal 1987 al 1993 il complesso fu oggetto di lavori di restauro commissionati dal dipartimento per i beni culturali di Mosca. Tuttavia, i lavori non si conclusero a causa del ritiro dei finanziamenti. Nel 1998 fu istituito il nuovo museo del Cremlino di Zarajsk, il quale comprende una collezione di dipinti e sculture provenienti dalla Russia, dall'Europa occidentale, dalla Cina e dal Giappone.
Monumenti
Le mura del cremlino si estendono su una superficie di 134 × 190 metri, formando un rettangolo. La struttura è dotata di 7 torri.
La cattedrale di San Nicola risale probabilmente al XIII secolo, ma fu ricostruita in pietra bianca e coronata di 5 cupole a bulbo nel XVII secolo. Al suo interno è custodita un'antica icona reputata miracolosa raffigurante il santo a cui l'edificio è consacrato.
La cattedrale della Decollazione di San Giovanni Battista fu costruita nella forma attuale tra il 1901 ed il 1904 nello stile tipico dell'architettura neoclassica. Negli ultimi anni è stata soggetta a numerosi interventi di restauro.