Со ослабувањето на Византија, во Македонија на сцена ќе стапи и ќе се зацврсти младата и експанзивна Српска феудална држава. Ваквите војни од освојувачки карактер, главно придонеле до уништување на јужна Македонија. Во 1283 година, жртва на еден таков продор ќе стане и Струмица, која заедно со Серската и Кавалската област ќе бидат опустошени.

По овој победнички поход кралот Милутин за прв пат ќе стигне до Егејското Море, но на крај ќе се повлече назад зад границата која тогаш се протегала северно од Струмица, Прилеп и Охрид.

Наредниот триесетгодишен период се одликува со релативно мирни односи помеѓу Србија и Византија, се до доаѓањето на престолот на српскиот владетел Стефан Душан (1331—1355). Со неговото доаѓање на власт, Струмица засекогаш ќе се ослободи од византиско владеење и во 1344 ќе потпадне под средновековната српска држава.

Годината на освојувањето на Струмица останала запишана во српските извори кои го опишуваат походот од 1334 година со следниов опис:

„А другите области и градови грчки (се мисли освоени од Грците б. н. ) што ги зазеде и присоедини кон земјата на својата татковина, и многу други земји… чии имиња се: прво, славниот Охрид, и славниот град Прилеп (во кој благочестивиот крал соѕида за себе двор за живеење), и пак славниот град Костур, и градот Струмица, градот Лерин… И сето ова го зазеде за три години од своето кралување… “

Од она што може да се заклучи од тие извори е дека, голем дел од македонските градови, меѓу кои била и Струмица, сами му се предавале на царот Душан, преморени од повеќе вековното непожелно владеење на Византија.

Многу интересен е податокот дека, Струмица пред да потпадне под Душан, повторно била мало независно кнежество. Тоа се должи на фактот што тука се се зацврстил самостојниот феудалец, протосевастот Хрељо, во српските народни песни познатиот „Реља Крилатица”. Според српскиот историчар Стојан Новаковиќ, уште во времето на Стеван Дечански српската граница кон Византија минувала јужно од Струмица, што значи дека градот повеќе не бил во Византиско владение.

Ваквото негово тврдење индиректно го потврдува и претходниот времеплов – писмото на Никифор Грегора, во кое тој го изложува своето сведочење дека по минувањето на Струма влегле „во туѓа земја”; и дека тука живееле „туѓинци”. Тој податок се поткрепува и со појавувањето на вооружената стража која ја исплашила византиската делегација на чело со Грегора, што укажува на тоа дека можеби се работело за гранична стража на преминот кон Струмица.

Постои и еден друг податок кој укажува на тоа дека Струмица и Штип биле дел од полунезависна држава кој може да се најде во светогорскиот манастир Хилендар. Имено, уште пред 1334 година пишаните документи покажуваат дека Хрељо на Хилендер му дарувал цркви, имоти и села заедно со селаните.

Во една од повелбите српскиот крал Урош III (претходникот на Душан) од 1328 година, запишана е дарбата на манастир „Свети Архангел” во Штип, кој Хрељо го подигнал како своја задужбина.

Од оваа одредба може да се види дека владенијата на Хрељо се простираат источно до селото Старо Коњарево („Кунарани”) и Кључ што посочува дека тука била границата на неговото владеење. Во оваа повелбата српскиот крал го наречува Хрељо „верни и многовозљубљени властелин” што посочува дека уште во тоа време тој веќе вил „полусамостоен владетел”, кој веројатно доброволно стапил во вазални односи спрема Србија.

Колку бил влијателен Хрељо може да се види и четири години подоцна, во една од првите повелби на Душан, издадена 1332 година во кој то го нарекува Хрељо „правоверни властелин кралевства ми. ”

За потеклото на Хрељо, не се знае многу, од пишаните извори кои се достапни, а се напишани од узурпаторот на византискиот престол, познатиот Јован Кантакузен се вели дека, „војводата Хрељо, кој владеел во Струмица и Петрич, бил од македонско потекло”, за нешто подоцна да го нарече – Србин.

Очигледно е дека Струмица низ целото средновековие била одлична почва за издигањето на независни владетели, затоа што издигнувањето на Хрељо, се случувало речиси под слични околности, како и претходните две на Хрс и Стрез.

Приказната на Хрељо навистина е интересна и покажува дека во Струмица, отсекогаш постоеле лукави и способни политичари, кои вешто балансирале помеѓу големите силе од тој период и во Струмица создавале независни кнежевства. Хрељо успеал да ги искористи династички војни на Византија. Во целиот тој хаос, со менување на сојузниците, успеал да ја зацврсти и прошири својата лична власт.

Хрељо добил три византиски титули една по друга: Протосеваст, Велик Доместик
и Ќесар. Најверојатно, Ќесар Хрељо ги добил сите титули од Византија во 1340 и 1341 година.

Најпрвин, Хрељо го искористил барањето на Урош III, и му помогна на Андроник II, во борбата против неговиот внук. Ваквиот потег му ја донел византиската дворска титула протосеваст. Кога во 1340 година Душан ќе пада тешко болен, Хрељо смело ќе го отфрли српското вазалство и кон своите територии ќе го приклучи и градот Мелник.

Но заплетот, што туку почнува. На сцена сега стапуваат нови императори во Византија. Во октомври 1341 година Јован Кантакузен се прогласил за византиски цар и дошол во Скопје, во 1342 година, со цел да склучи сојуз со цар Душан, па заедно да војуваат против императорот Јован V.

На средбата во Скопје, Душан инсистирал да се вметне и Хрељо, т.е да му биде предаден затоа што имаат нерасчистени сметки, а во тоа време Хрељо веќе бил во сојуз со Кантакузен. Кантакузен не се согласил со ваквиот предлог. Но, ваквиот развој на настаните го натерал Хрељо уште пред да биде случен сојузот да испрати писмо до цар Душан, во кое го молел за прошка, и ја заветил Струмица и себеси за иден српски вазал.

Ваквиот лукав потег бил успешен, и на овој царски сојуз бил придодаден и Хрељо, а неговата независност гарантирана. Воениот сојуз кој Душан и Кантакузен го склучиле имал за цел да ги прошири нивните територии па така за нивна прва цел бил одбран градот Серес. Токму за време на опсадата на овој град Хрељо тешко се разболел и решил да се замонаши во манастирот кој самиот го изградил – Рилскиот манастир. Притоа го зел и монашкото име Харитон. Набргу тука и ќе почине.

Во една повелба од март 1343 година, јасно се гледa дека Струмица му се предала на Душан без отпор. Имено, со оваа повелба Душан му потврдил дел од дотогашните привилегии и имоти на некој си „властелин на Струмица Рудл”, што овој ги имал добиено како наследство од Хрељо.

Во повелбата исто така се споменува дека Рудл, управувал со Струмица само кратко време, т. е. до доаѓањето на Душан. Во повелата се вели дека Рудл, „властелин града того”, т. е. на Струмица свечено му ја предава на Душан, чии вазал е.

Покрај српските, и византијските извори го спомнуваат Хрељо во пишана форма. Во тие историски писанија тој е окарактеризиран како мошне богат и силен феудалец; човек кој „меѓу благородниците од својата нација со храброст и со сите воени почести се величаше” и кој во својата столнина Струмица имал „тврдина што се издига кон облаците”. – уште еднаш потврдувајќи дека во овој период Цареви Кули биле важна тврдина на Балканот.

По смрта на Хрељо следува нова интересна епизода во струмичката историја.