У историјским изворима Врање се први пут помиње 1093, у време напада жупана Вукана на византијску војску. Марково кале, средњовековни утврђени град, налази се на истуреном гребену између планине Пљачковице и Крстиловице, изнад ушћа Мале у Деветинску реку. Конфигурација терена је диктирала троугаону основу утврђења. Утврђење је са јужне и источне стране опасано масивним бедемима, док је западна страна брањена природним стенама. Дебљина бедема износи око 2 m. Лице зида је грађено од ломљеног камена, а унутрашњост је испуњена трпанцем и кречним малтером. Бедеми су имали шетну стазу која се завршавала зупцима. Сачувани су остаци југоисточне угаоне куле, мањих димензија. На северној страни, утврђење се завршава бранич-кулом квадратне основе, која је сачувана у висини две етаже. Унутрашњост града се дели на горњи и доњи стамбени плато. На горњем платоу откривене су две цистерне – једна кружне, а друга ромбоидне основе, и три просторије мањих димензија. У доњем стамбеном платоу откривене су мања просторија квадратне основе и остаци цркве, основе у облику слободног крста са тространом апсидом. Према резултатима археолошких истраживања може се закључити да је било дрвених грађевина за становање.