La première forteresse édifiée sur le site remonte à l'époque romaine ; elle protégeait alors la route qui mène à l'actuelle Bulgarie. En 530, elle a été restaurée et agrandie par les Byzantins et, à l'époque des Nemanjić, protégeait la frontière avec l'Empire bulgare. Sous le règne du roi serbe Milutin (1282-1321), à l'époque de la lutte contre Drman et Kudelino à Ždrelo, Vrmdža cesse d'être une forteresse frontalière. Au début du XVe siècle, avec les forts de Bovan, Stalać et de Lipovac, elle a été frappée par la guerre civile dans l'Empire ottoman et, en 1412, le sultan Musa Çelebi s'est emparé de toutes ces places fortes. Le sultan a trouvé la mort peu après dans une bataille à laquelle participait le despoteStefan Lazarević qui reprend ces citadelles[réf. nécessaire].
