По смртта на Стрез и нејзиното освојување од Епирците, следува нов турбулентен период за Струмица.

Во 1230 година Епирците ќе се судрат со Бугарското царство во битката кај Клокотница, во денешна јужна Бугарија, и со губењето на таа битка ќе ја изгубат и Струмица. Со тоа Струмичката област, во наредната декада, ќе биде вклучена бугарското царство на Иван Асен II. Но, ни Бугарите нема да може да ја задржат Струмица за долго. Во 1261 година кога Византија ќе биде обновена, Струмица повторно ќе биде од нив освоена, и со тоа се става крај на период во кој владетелите на градот брзо се менувале.

Византиското владеење ќе потрае во наредните стотина години. Токму во последните години на нивното владеење, ќе биде напишан еден мошне ценет опис на градот и на неговата околија, кој и денес е зачуван. Него ќе го направи византискиот историчар и писател Никифор Грегора. Имено, Грегора кој патувал со мала воена придружба, во една дипломатска мисија во Србија, поминувал низ Струмица. Па така во 1326 година тој неколку дена ќе се задржи во Струмица, што ќе му овозможи да го види градот одблиску.

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

Следува доста интересен настан кога доцна во ноќта пред Византијците изненадно се појавила група локалци, кои биле вооружени со лесно оружје, копја, секири, а некои од нив носеле и стрели.

„Изненадување и страв одеднаш ги фати нашите луѓе”, зошто се нашле „во туѓа земја и во такво (ноќно) време. Живеејќи во оваа земја, и свикнати да прават заседи по клисурите, тие можеа да се борат со нас, кои бевме туѓинци”, вели Грегора. Сепак до напад и пресметка не дошло, а вооружените „варвари”, т. е. Македонци, со неколку зборови објасниле дека на ова место стоеле за да „ги бранат патиштата, реките, од оние што би посакале тајно да се префрлат во соседните краишта за пљачкање”.

Во овој дел од писмото јасно се гледа дека во котлината владеело беззаконие и локалното население само се штитело од напади и разбојници.

Многу интересен е фактот што на неколку места во писмото Грегора се споменува дека во овие краишта се зборувало на „еден варварски јазик”; дека локалците не го знаеле грчкиот јазик; и дека со вооружената стража во клисурата можеле да се разберат, благодарејќи на тоа што меѓу Византиjците имало некои кои „донекаде го знаеја нашиот јазик”.

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

Во наредниот дел од писмото Грегора се фокусира на Струмица и неговото име. Тој споменува дека мештаните градот го викаат Струмица по своето словенско-македонско име, а не по името Тибериопол, кое е официјалното име на градот. Понатаму во писмото тој ја опишува струмичката тврдина за која вели:

сместена е врз една стрмна планина, така ѓаволски издигната, што оние што седат на нејзините ѕидови личат на не знам какви птици кога човек ги гледа од рамницата”.

Оваа писмо претставува вистинско историско богатство за Струмица затоа што Грегора се затекнал во Струмица за време на Велигденските празнувања. Имено, тој го дава следниов опис:

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

Оттука можеме да видиме дека во овој период, Цареви Кули и понатаму се значајна тврдина во која имало сместено гарнизон со војници, а под ѕидините постои живописен град. Од прославите опишани во писмото може да се види дека орото како културен македонски израз веќе постои, и е широко распространето при прослави на големи настани.

Писмото на Грегора продолжува со малку подетален опис на Струмица и нејзиното население.

Тој продолжува да се жали дека е далеку од престолнина и дека јазикот на луѓето кои ги среќавал е всушност „овчарски и планински”; а струмичани ги опишива како „луѓе кои ја сметаат за глупост… сета ритмичка и хармонизирана музика на светите химни”; а Струмица и Македонија како „туѓа и варварска земја”.

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

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