Веднаш по Беласичката битка и падот на Македонската средновековна држава, водена од Цар Самоил, Струмица и Македонија, потпаднале под византиска управа. Тоа значи дека во Струмица бил воведен византискиот тематски управен систем. Василиј II решил да не го менува даночниот систем кој бил воведен од Самоил па тоа придонело во Струмица, првовремено, состојбата на населението барем финансиски значително да не се влоши.
Но, како што споменавме, поради големата лојалност која Струмица ја покажала кон Самоил и Македонската држава, Византијците решиле да го изменат етничкиот состав на феудалците и населението. Па така, на сите управни служби наместо Словени, биле поставувани Грци. Со ваквиот тренд особено била погодена словенската писменост и култура, затоа што сите високи црковни функции исто така дошле во рацете на Грци.
Токму во овој период и во Струмица а и пошироко во Македонија ќе почне да се среќава грчко население, кое главно се бавело со административни функции. Од овој период постои еден интересен податок кој можемо да го извлечеме од еден попис („практикон”) на манастирските имоти во Струмичката област од XII век, каде како сведоци се потпишале дванаесетмина видни граѓани, меѓу кои, само половината биле Словени. Од овој попис може да се види дека командантот на Цареви Кули, со византискиот гарнизон во неа и со епископот и неговите помошници, биле Грци и византиски поданици.
Овој попис покажува дека во Струмица во тој период имало околу десетина попови кои богослужеле, а од нив само четворица имаат словенски имиња, додека останатите шестмина носат грчки имиња. Другиот интересен факт е тоа што само меѓу видните и поимотни луѓе можеле да се најдат Грци, што наведува на заклучокот дека и покрај присилното иселување кое следело, најголемиот дел од населението, особено во селата, си останало македонско.
Василиј II, не застанал со уништувањето на Македонската средновековна држава па така решил да ја деградира и Охридската патријаршија, во ранг на автокефална (самоуправна) архиепископија, потчинувајќи си ја директно под своја власт.
За нејзин прв архиепископ бил поставен Јован, за кого се смета дека бил македонец, но веќе по 1037 година, со доаѓањето за Охридски архиепископ на Гркот Леон, и оваа важна црковна функција ќе падне во рацете на Грци. Василиј II издал и три повелби (грамоти) кои се однесуваат на Охридската архиепископија.
Овие повелби се значајни затоа што од нив дознава и територијалниот обем на Самоиловата држава. Струмица се споменува уште во првата „грамота“ издадена 1019 година, каде се споменува како Струмичка епархија. Во оваа грамотата уште се определува и бројот на закрепостените селани, клирици и парици, што ќе им се даваат на епископите.
Струмичката епархија го зазема петтото место од овој список а за неа е речено следново:
„Епископот на Струмица да има во самата Струмица, во Радовиш и во Конче 12 клирици и 12 парици”.
Што значи дека Струмица продолжила и во византиско време да биде седиште на епископ. Седиштето на Струмичката епархија продолжила да биде Водоча. Она што дополнително го зајакнува значењето на Струмица за Византија во тоа време е тоа што градот станува седиште и на тема, со која управувал византиски стратег.
Уште една друга промена која навистина ја погодило Струмица е тоа што со воведување то на византиското владеење се зголемила и експлоатацијата на македонските народни маси. Овој процес на струмичани им носел губење на личните слободи и закрепостување, бесконечно зголемување на државните, црковните и феудалните ангарии, даноци и такси, а честопати и најотворено пљачкање.
Ваквата состојба на населението ќе придонесе во XI век да се кренат две поголеми, но неуспешни востанија. Тоа биле востанијата на Петар Делјан во 1040 и на Ѓорѓи Војтех во 1072 година. Интересен е податокот што овие востанија не се прошириле во Струмица, што покажува дека поради своето стратешко значење Струмица била по силна контрола.
Колку значаен регион за Византијците била Струмица потврдува и фактот што на самиот почеток од XII век таа пак се споменува во византиските извори. Имено, Византискиот императорот Алексеј I Комнен при една своја турнеја низ империјата решил да ја посети и Струмица.
Неговиот престој во Струмица во 1106 година го искористил за да го посети ново основаниот манастир „Света Богородица Елеуса”, во селото Вељуса, при што на манастирот му подарил земји и имоти.
Крајот на XII и почетокот на XIII век во историјата на Македонија а и Струмица, ќе донесат нови бурни времиња. Завладеала крајно тешка и анархична состојба, во која несигурноста за животот и имотот на населението опасно се зголемиле. Моќта на Византија а со тоа и нејзината контрола над Струмица почнала брзо да опаѓа. Династички борби за престолот, стремежот на крупните феудалци за самостојност и нивните борби како меѓу себе, сериозно ја ослабеле централната власт. Надворешните фактори, како што се нападите на Кумани и Печенеги од север, на Венецијанци, Нормани и крстоносци — од запад, придонеле до непослушност на струмичани кон Византија.
Во 1204 година крстоносците ќе го освојат и опљачкаат Цариград, со што ќе ја разбијат Византија. На нејзино место во наредните 50 години ќе изникнат неколку мали латински и византиски државици. Во исто време на балканската политичка сцена се појавуваат средновековна Србија на Немањиќите (по 1170 година), и таканареченото Второ бугарско царство, по востанието, кренато во 1185 година. Во условите на слабеење, а потоа и привремено пропаѓање на Византија, на успешните ослободителни востанички и други борби на Срби и Бугари, и во Македонија се појавиле сепаратистички стремежи кај крупните феудалци.
Ваквата состојба ќе доведе до создавање на независна Струмичка држава, под водство на двајца различни феудалци, Хрс и Стрез.