It dates from the end of the 14th or early 15th century, and according to legend, was built by two brothers from the Vojinović noble family.

It was built over the Sitnica river, which lay on the trade route between Dubrovnik and Skopje and neighbouring parts of the Balkan peninsula.

The Vojinovići existed as nobility in the first half of 14th century, and according to epic poetry were nephews of Emperor Dušan.

However, Vushtrri itself was outside their area of control, which was expanding to the nearby Zvečan, even at the time of their greatest power under the Vojislav Vojinović (around 1355–1363) and Nikola Altomanović (1366–1373).

However, in Vushtrri in the early 15th century, the court of the House of Branković is mentioned, who were related to the Vojinović family.