Gradac was mentioned around 1315. However, the district of Budimlje had been mentioned a century earlier, when one of the first bishoprics of Raška had been established there. According to Jirecek, the Budimlje district was named after the fortress of the same name. If we accepted this as truth, than the older name of Gradac would be Budimlja and it would account for a relatively late mention of this fortification in written sources.
The fortification had an irregular, slightly elongated plan, laid in the east-west direction, and an outer defensive wall towards north. Based on the portable finds from the locality, we can conclude that the fortification had been used even before the Middle Ages. A detailed archeological research might provide data connecting Gradac with the mention of this name by emperor Constantine Porphyrogenitus.
The fortress had a suburb at the site of today's village Budimlje, where old graveyards and the remains of a church are found.