Армии снабжались из различных источников. Начиная с IV по VII в., все войсковые подразделения обеспечивались продовольствием. С конца V в. на востоке на пропитание выделялись денежные средства, на которые полковые уполномоченные покупали непосредственно у производителей или на рынке провиант и все необходимое для солдат, а потом распределяли между ними. Мобильные подразделения получали необходимую часть из доходов провинций, расплачиваясь за них расписками для учета в налогообложении на будущий год. Администрация префектов следила за тем, чтобы военные поставки были учтены при налогообложении. О прохождении через регион воинских частей местные власти извещались заранее, чтобы они имели возможность разместить припасы вдоль маршрута следования войска.
Все необходимое — одежду, вооружение, коней — армия получала посредством натуральных поставок, а также из государственных мастерских. В городах империи работали несколько оружейных заводов. С конца VI в. оружие и одежду для армии можно было также купить из специально выделенных для этого государственных средств. Коней армия получала благодаря натуральным налогам, а кроме того, их покупали у владельцев по твердым ценам; часть лошадей поставляли с имперских конных заводов. Железная руда, уголь и дрова поступали в армию также благодаря натуральным налогам.
После кризиса, вызванного исламским завоеванием во второй половине VII в., в этой системе произошли значительные изменения. Основная тяжесть расходов по содержанию армии была переложена на плечи местного населения. Денежные выплаты военным были существенно урезаны и была создана система натуральных налогов на содержание войск непосредственно с местного населения. Благодаря натуральным налогам войска получали оружие, одежду, лошадей и вьючных животных. Для этого войска были широко распределены по регионам, в результате чего возросла зависимость армии от личных солдатских хозяйств как в области провианта, так и вооружения. В конце VIII столетия многих провинциальных солдат призывали в армию только на сезон. При этом оружие, верховые и вьючные животные поставлялись по натуральному налогу. Однако, несмотря на все изменения в системе снабжения армии, в этот период оставалось много общего с той, какой она являлась до 650-х гг., и к IX столетию она, хотя в урезанном и деформированном виде, сохранила прежнюю, позднеримскую основу.
Возникшие в VII–VIII столетиях структуры носят обобщенное название «системы фем». Восстановление относительной политической и экономической стабильности в империи, а также раздоры среди ее врагов позволили Византии к 800 г. добиться некоторой стабильности. Несмотря на несколько серьезных поражений, империя в целом проводит более активную, наступательную политику и на востоке, и на севере, сочетая, как например против болгар, военные действия с миссионерской и дипломатической деятельностью. Несмотря на ожесточенное сопротивление мусульманских эмиров в первой половине X в., Византия смогла успешно отвоевать у них многие земли в северной Сирии и Ираке, разгромить Второе Болгарское царство и начать повторное завоевание Сицилии и южной Италии. Ко времени кончины императора Василия II (1025), Византийская империя снова превратилась в могущественную державу Средиземноморья, соперничать с которой мог только Фатимидский халифат в Египте и Сирии.
Наступательный характер войн середины IX в. оказал значительное влияние на военную организацию империи. Ополчение провинций не могло более эффективно выполнять новые задачи, и потому стали формироваться полевые армии с более сложной тактической структурой, более совершенным вооружением, имеющие специальные боевые навыки и боевой дух; руководящую роль в этих войсках постепенно приобрела военно-землевладельческая знать провинций. Полностью профессиональные военные части играют все большую роль по мере того, как государство переводит оплату военным в денежную форму и на эти деньги берет на службу наемников. В результате появляется пестрая интернациональная армия, в которой наряду с местными профессионалами, как в пехоте, так и в кавалерии служат русы, норманны, турки, франки и т. д. Быть может, наибольшую известность приобрела варяжская гвардия — варанги, впервые сформированная при Василии II и состоявшая из скандинавских наемников, искателей приключений. Среди их командиров самым знаменитым был Гаральд Гардрад, позднее, в 1046–1066 гг., ставший королем Норвегии и принявший смерть от руки английского короля Гаральда Годвинссона в 1066 г. в битве при Стамфордском мосту. Гаральд Гардрад воевал в составе варяжских частей в 1034–1041 гг.