Nonostante le controversie sulle origini del Castello gli scienziati concordano su un punto - nel primo periodo del II millennio c'era una palizzata di legno, eretta per proteggere parte del principato di Galizia-Volinia. Dopo un incendio su larga scala nel XIII secolo, il legno venne sostituito con la pietra.