With the loss of most of the Balkan hinterland to the Slavic and Bulgar invasions in the 7th century, however, the authority of the prefect (in Greek eparchos, "eparch") was largely confined to the city and its immediate surroundings.

[1][2] The strategos of Thessalonica is attested for the first time in 836, but a letter of Emperor Michael II (r. 820–829) to the Frankish king Louis the Pious (r. 814–840) may indicate the theme's existence already in 824.

[3][4] The historian Warren Treadgold dates the theme's creation to c. 809, during the anti-Bulgarian campaigns of Emperor Nikephoros I (r. 802–811) which extended Byzantine rule to the city's hinterland.

Its western and northern bounds were undetermined, fluctuating with the tide of war between the Byzantines, the local Slavic tribes, and the Bulgarians.

[7] Under Emperor John I Tzimiskes (r. 969–976), a doux who commanded the professional tagmatic troops stationed in the theme was installed in the city, and seems to have co-existed for a while with the strategos, before assuming the latter's duties as well.