According to the later tradition and forged documents he came out from the noble family of Ohmućević. He appears for the first time in the history of John Kantakuzenos. In December 1327 he commanded a Serbian auxiliary contingent of twelwe cohorts laying between Drama and Philippoi in support of the Byzantine Emperor Andronikos II. against his grandson Andronikos III. (τοῦ δὲ ἐκ τῶν Τριβαλῶν συμμαχικοῦ, δυοκαίδεκα ταγμάτων ὄντων, ὁ Χρέλης ἐστρατήγει, τῶν τε παρὰ Τριβαλοῖς εὐπατριδῶν καὶ ἀνδρίας καὶ ἐμπειρίας στρατηγικῆς τὰ πρῶτα φέρων παρ’ αὐτοῖς). 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. The inscription on the tower testifies that by the time of its construction Hrelja still acknowledged Serbian suzerainty bearing the tile of protosevast ((Pri državě gospodina prěvysokago Stepana Dušana kraal sьzyda sьn pirgь gospodinь protosevastь Hrelь sь trudomь velikomь i eksodomь svetomu ōtcu Iōanu Rylskomu i materi božii naricaeměi Ōsěnovica vь lěto 6843 indiktiōnь 5). Sometimes between 1336 and the june 1341 Hrelja deserted from the Serbian king Stefan Uroš IV Dušan. In early 1342 he made contact with Kantakuzenos. It is not clear when he first met Hrelja, though he does refer to Hrelja as being a friend for the most part and that it was through his own initiative that Hrelja came to know Andronikos III. (ὁμοίως δὲ καὶ Χρέλης, ὃς ἦν πρότερον πρὸς Ἀνδρόνικον τὸν βασιλέα ηὐτομοληκὼς ἐκ Τριβαλῶν, στρατιώτας τε ἔχων χιλίους καὶ πόλεις τρεῖς παραδεδωκὼς, ἃς Ῥωμαίων οὔσας ὑπηκόους κατὰ τὸν πρὸς ἀλλήλους τῶν Ἀνδρονίκων βασιλέων πόλεμον κατέσχον οἱ Τριβαλοὶ, τῶν κατεχόντων Ῥωμαίων παραδόντων· οὗτος δὴ οὖν ὁ Χρέλης χρήμασί τε ἐῤῥωμένος καὶ στρατιὰν ἔχων ἀξιόλογον ὑφ’ ἑαυτῷ καὶ πρότερον βασιλεῖ τῷ Καντακουζηνῷ ἐς τὰ μάλιστα φίλος ὢν, (δι’ αὐτοῦ γὰρ καὶ Ἀνδρονίκῳ προσῆλθε τῷ βασιλεῖ,) πέμψας καὶ αὐτὸς, ὅτι τε αἱροῖτο ἐδήλου τὰ ἐκείνου, καὶ παρῄνει καὶ αὐτὸς πρὸς τὴν ἑσπέραν μᾶλλον τρέπεσθαι, ὡς οὐ φαύλης τινὸς αὐτόθεν ἐσομένης ὠφελείας). The Kantakuzenos' statement and the fact that he handed over one thousand soldiers and three cities gives a picture of Hrelja's wealthiness, which is confirmed also by the forged charters concerning the Hrelja's donation of the Church of St. Archangel Michael in Štip to the Monastery of Hilandar.