Трёхнефная базилика св. Таксиархов (т.е. Чиноначальников архангелов Михаила и Гавриила) у Митрополии, также относящаяся к IX–X вв., расположена довольно далеко от древнего ядра города. Скорее всего, по мнению исследователей, она была кладбищенской церковью, о чём свидетельствуют более поздние изображения усопших касторийцев на её стенах. Регулярное упоминание Кастории в источниках начинается с описаний болгаро-византийских войн конца Х в. В Х в. Касторию (болгарский Костур) дважды завоёвывали болгары – при царе Петре (927–948 гг.) и при царе Самуиле (997–1014 гг.). В 1018 г. Кастория была возвращена в состав Византийской империи императором Василием II Болгаробойцей. К началу XI в. исследователи относят строительство одной из самых известных византийских церквей города – трёхнефной базилики св. Бессребреников в квартале великомученика Пантелеимона. В хрисовуле Василия II, касающемся автокефальной Охридской архиепископии (1020 г.), Кастория стояла на первом месте из 31 епископии, подчинённой Охриду, и поэтому именовалась «первопрестольной». Согласно этому документу, Кастории подчинялись Корестия, Колония, Девол, Воюса (Вооса) и Мор. Из данного хрисовула исследователи сделали вывод, что в Х в. Касторийская епархия входила в состав Болгарского патриархата, т.к. в тексте говорится, что Охридский архиепископ «владеет и управляет всеми болгарскими епископствами, которыми при царях Петре и Самуиле владели и управляли тогдашние архиепископы». Иван Снегаров предположил, что при этих царях территория будущей Касторийской епархии была частью Девольской епископии, а Василий II перенёс центр этой церковно-административной единицы в Касторию. По мнению Петра Коледарова, Мор – это горный массив Тмор (Томор, Томори) в северо-западной части Девольской епископии. Девол, с которым связана деятельность равноапостольного Климента Охридского, в период Первого Болгарского царства являлся центром Девольской епископии. Хотя Девольская епископия была присоединена к Касторийской при реорганизации в 1018–1019 гг. Болгарской церкви Василием II, уже в конце XI – начале XII вв. она была отделена от неё. О епископах Кастории византийского периода сохранились крайне скудные сведения. Печать первого названного по имени Касторийского епископа Иоанна Раймон Жанен относит к эпохе Комнинов, а В. Лоран – к Х в. О существовании в XI в. епископа Феодора известно исследователям тоже благодаря сохранившейся печати. Жившие во время архиепископства Феофилакта Болгарского (конец XI – начало XII вв.) Касторийский и Белградский епископы были выбраны из учёных мужей Константинополя. Автором Жития преподобного Антония Нового Веррийского был Касторийский епископ Кир (иногда в научной литературе ошибочно называемый Кириллом), время жизни которого исследователи приблизительно относят к XI–XII вв. В 1071 г. Кастория выдержала осаду болгарского войска Константина Бодина (впоследствии болгарский царь Пётр III), в 1082–1083, 1096 и 1185 гг. была захвачена норманнами. По мнению исследователей, в память об изгнании норманнов в 1083 г. византийскими войсками был построен и украшен фресками храм монастыря Мавриотисса на берегу озера Кастория, в 3 км от города, – по преданию, именно на том месте высадились император Алексей I Комнин и полководец Георгий Палеолог перед штурмом крепости.