Поселення Клевань, за твердженням істориків, існувало вже в XII столітті під назвою Коливань (коливань — назва ваг великого розміру, на яких зважували велику рогату худобу). Клевань розбудовувався на високому правому березі річки Стубли, по якій з 1793 року і певний час по тому, проходив польсько-російський кордон.
У письмових джерелах Клевань вперше згаданий під 1458 роком як власність князя Михайла Чорторийського. Як Олику прославили і розбудували князі Радзивіли, так і Клевань непорушно пов’язаний в історії із князями-магнатами Чорторийськими.
Природа сама підказала місце для замку — високі правобережні пагорби річки Стубли були дуже зручними для укріплення. На одному з прибережних мисів, який називають Городище, 1475 року князь Михайло Чорторийський — брацлавський намісник, побудував замок. У 1495 році за сприяння його сина Федора, луцького старости, замок було добудовано та оточено його міцними кам’яними мурами і глибоким ровом, який заповнювався водою Стубли. Тоді ж по кутам було зведено дві муровані вежі «пунтоне» — п’ятикутні в плані. Одна вежа захищала в’їзну браму, а інша — контролювала підступи до замку з боку річки. Обидві вежі відносно непогано збереглися, особливо східна. Товщина їхніх цегляних стін у деяких місцях сягала 3,8 м. Третя башта, що не збереглася до наших днів, була дерев’яною. Закінчилася побудова замку в 1561 році.
