Hrelja was first mentioned in the 1320s as the commander of a Serbian military detachment involved in that time's Byzantine civil war. With his detachment, Hrelja assisted Byzantine Emperor Andronikos II Palaiologos. By that time, Hrelja was already the ruler of a large domain in the region of Štip (in today's North Macedonia) and east of the city; in the early 1330s, his domain expanded to include Strumica. In 1334–1335, Hrelja reconstructed the church of the Rila Monastery and built the so-called Hrelja's Tower, the monastery's defensive tower and its oldest structure surviving today.^[3]

The stone tower is 23 metres (75 ft) high and has an almost square foundation. There are five stories, not counting the cellar, with a chapel devoted to the Transfiguration of Christ on the top floor; the chapel features fragments of 14th-century frescoes. The tower has a single entrance on the first floor, at the time probably reached through a ladder; from the entrance, the chapel can be accessed using the stone stairs built into the walls. It is thought that Hrelja's Tower was used as a protection for the monks, as well as a cache for valuables, a jail or a place to isolate mentally-ill people. A two-storey belfry was attached to the tower in 1844. Since 1983, the tower has been under UNESCO protection as part of the Rila Monastery, a World Heritage Site.^[4]

The inscription on the tower testifies that by the time of its construction Hrelja still acknowledged Serbian suzerainty:

During the rule of the most supreme lord King Stefan Dušan, lord Prōtosebastos Hrelja, with great work and at a great expense built this tower to the holy father saint John of Rila and to the Mother of God, called Osenovitsa, in the year 6843 indiction fifth. [1334–1335]^[5]

Hrelja donated real estate in the valley of Strumica to the Hilandar monastery, another fact testifying to his economic power; Hrelja also sponsored the construction of the Church of St Michael in Štip. In the late 1330s, Hrelja broke away from Serbia and became an autocrat with his capital at Strumica; he formally recognized Byzantine authority, but had vast political autonomy. Factors that contributed to Hrelja's decision to break away from the Serbian realm included his economic independence, his own armed forces and the frontier location of his estate, bordering the Second Bulgarian Empire and the Byzantine Empire to the northeast, south and southeast.^[3]

With another Byzantine civil war in the early 1340s, Hrelja was sought as an ally by both sides. Hrelja supported John VI Kantakouzenos, who awarded him the city of Melnik and the title of prōtosebastos. However, Hrelja did not actively engage in the conflict and pursued his own interests.^[3]

After Kantakouzenos suffered some heavy losses in the civil war and retreated to Stefan Dušan's court in the summer of 1342, he agreed to sacrifice his ally in return for Serbian support. Although Hrelja once again recognized Dušan's suzerainty and ceded the city of Melnik, he died on 27 December 1342 in the Rila Monastery. According to Bulgarian sources, He is said to have been killed by Serb mercenaries, hired by Emperor Stefan Dušan.^[6] Shortly prior to his death Hrelja had become a monk in the monastery under the name of Hariton. He was buried in the church he had reconstructed in the Rila Monastery. His epitaph testifies that he was awarded the title of caesar, most likely by John VI.^[1][3]

In Bulgarian and Serbian epic folklore, Hrelja (Relja Krilatica) is glorified as an ally of Prince Marko and a protector of the people against the Ottoman Turks.^[7][8]

Serbian and Bulgarian rulers were emulated by their nobility. After the time of King Milutin, Hilandar's property was significantly enlarged by the additions of many metochia with their land and income such as Holy Archangels' at Štip, the donation of Hrelja.^[9]

• Hrelja on Istorijska biblioteka (in Serbian)