Под влиянием завоеваний арабов-мусульман, в византийской армии произошли фундаментальные изменения. К самым важным из них можно отнести учреждение регионального и столичного войска. В конце VI века император Морис основал на Востоке военные поселения. Однако, остается не совсем ясным, когда именно появились первые провинциальные войска: во время правления императора Гераклия или после того, как мусульмане стали совершать набеги вглубь Анатолии. Было установлено, что семья солдата наследует его воинские обязанности. Трудность получения оплаты воинами подразделений, рассеявшимися во время хаоса мусульманских набегов, заставляла солдат обосновываться на постоянном месте жительства и даже устраиваться на временную работу.
Первое подразделение вновь появившегося регионального войска называлось «Опсиконом». Несколько лет спустя были образованы еще два – «Анатоликон» и «Армениакон». Подразделение «Опсикон» до конца VIII века в результате поднятого им мятежа утратило прежнее положение и стало рядовым подразделением регионального войска. Подразделения «Анатоликон» и «Армениакон» оказались более боеспособными, чем «Опсикон». Из-за продолжающихся набегов мусульман граница Византии была разделена на небольшие участки, называвшиеся клейсораи. Количество региональных войск в то время здесь было небольшим, в отличие от поздневизантийского периода, последовавшего за войной 742 года.
В VII-VIII веках возросшая сила провинциальных войск привела к ненужному соперничеству, в результате которого различные подразделения этих войск могли оказаться по разные стороны баррикад во время гражданских войн, часто имевших место в Византии. Правительство позволило воинам провинциальной армии приобретать землю в собственность. Это не значило, что солдаты становились фермерами, они просто жили на доходы со своей земли так же, как средневековые рыцари. Ядром провинциальной армии были хорошо снаряженные воины, находившиеся на постоянной службе, как это было в Тагмате – подразделениях столичного войска. Некоторые из них жили в поместьях, другие – в казармах. Снаряжение для бедных воинов приобреталось на деньги земляков из родной деревни, состоятельных землевладельцев или военного руководства провинции. Представители аристократии служили кавалеристами, простые люди – пехотинцами.
У воинов провинциального войска была большая перспектива роста. Например, Лео III (717-741), некогда служивший в их рядах, стал впоследствии императором. В VIII веке старые доместики вошли в состав «Сколы», которая, будучи реформирована Константином V (741-775), снова стала играть присущую ей роль. Подразделение спатариев, основанное Феодосием II в V веке, изначально состояло из евнухов, вооруженных мечами. С VII века в его состав входили подающие большие надежды юные командиры, имевшие помимо хороших физических данных отличную боевую подготовку. Императрица Ирина (797-802 г.г.) сформировала собственное подразделение телохранителей, известное под названием «Вигла». Оно было выделено из состава провинциального войска, стоявшего во Фракии. Однако, после смерти императрицы это подразделение утратило свой статус.
В столице располагались войска, называвшиеся Тагмата, каждое тактическое подразделение которых состояло из 300 человек. Десять подразделений «тагмата» составляли один полк, называвшийся меросом. Мерос, в свою очередь, состоял из двух-трех мойр. Теоретически армия состояла из трех меросов. В начале IX века император Никефор (802-811) разделил Тагмату на императорскую и провинциальную. Императорская Тагмата по-прежнему располагалась в окрестностях Константинополя. Он также учредил полк «Икантой», вероятно являвшийся тренировочным подразделением для курсантов военного училища. Солдаты Тагматы теперь были защищены законом от суровых наказаний в случае провинности, имели более высокую оплату и лучшее снаряжение, чем другие войска. Тем не менее, воины византийской армии все равно время от времени поднимали восстания. Наибольшее беспокойство доставляло императору фракийское провинциальное войско, расположенное ближе всего к столице. В VII веке даже элитные подразделения устраивали бунты, реагируя таким образом на задержку оплаты. Причинами беспорядков могли быть также неумелое руководство армией, поражение в бою, потеря территории и даже недовольство государственной политикой в целом.
Граница Византийской империи с мусульманами проходила по Таурусским горам и севернее – по направлению к Грузии. После завоевания Сицилии и Малатии Умиадским халифатом в конце VII – начале VIII века имело место одно существенное изменение: Каппадокия стала штабом и плацдармом византийского движения сопротивления. С течением лет присущие воинам противостоящих сторон черты стирались: солдаты стали менять вероисповедание, с удивительной легкостью переходя из православия в ислам.
Власть Византии в большинстве западных провинций ослабла. Например, на территории, занимаемой современной Албанией, войско держалось на преданности семейным и племенным традициям. В 697-698 г.г. народ итальянской Венецианской лагуны принял решение об основании собственного герцогства. Однако, выборы дож, как и прежде, должны были происходить с одобрения Константинополя. В 726 году византийцы, проживавшие в Равенне, успешно сопротивлялись возраставшему давлению со стороны империи, когда их собственные ювены нанесли поражение византийским экспедиционным силам. Равенна была разделена на 12 кварталов. Население одиннадцати из них давало армии воинов, которых отправляли на помощь гарнизонным подразделениям. Выходцы из двенадцатого квартала становились служителями церкви. Другие части Италии, находившиеся под контролем Византии, страдали от периодических набегов ломбардцев. Самую эффективную защиту от них удалось организовать Папе Римскому, а не императорскому правительству Константинополя. Небольшая армия города Рима, сформированная по тем же принципам, что и другие византийские войска, являлась основной силой итальянцев. К концу VIII века большая часть этой армии состояла из ополченцев. Имелось также небольшое подразделение – ополченцы «Сколы». Каждое подразделение, имевшее свой флаг, возглавлял патрон из аристократов города Рима. В 800 году Папа короновал Карла Великого в качестве императора. С этих пор Рим вместе с прилегавшими к нему территориями навсегда перестал быть частью Романо-Византийской империи.
