Императорские войска теперь сражались во имя торжества Христа. Согласно декрету императора Феодосия II от 416 г., в армии могли служить лишь христиане. После утренней и вечерней трапезы в войсках рекомендовалось провести церковные богослужения, по окончании которых все собравшиеся должны были «пропеть Трисвятое и все остальное, что полагается». Священники, прикрепленные к каждому полку, регулярно служили походные молебны, обязательные для всех, советовали обращаться с молитвами к святым, покровителям воинов, например, к Св. Михаилу, Св. Георгию или Феодору Тирону («Новобранцу»). Императоры снабжали армию святой водой и призывали ее воевать во Имя Господа. Поэтому любое столкновение, в котором участвовали ромеи, считалось справедливой войной, тем более, если она велась с презренными язычниками-варварами или инородцами-эфниками, не исповедовавшими ортодоксального православия.
В V–VI вв. армия делилась на две основные ветви: пограничные войска — лимитаны (limitanei) и мобильные войска, называвшиеся комитатами (comitatenses). Последние назывались так, потому что служили под началом военных комитов, которыми в свою очередь командовали военные магистры — по-латыни магистры милитум (magistri militum). Лимитаны — «пограничники» набирались на месте. Они несли службу, главным образом, на Евфрате и Дунае, защищая фортификационные линии Империи, пока те еще продолжали действовать. Остальные войска-комитаты представляли основное ядро армии. Это были воинские подразделения, отчасти набиравшиеся из рекрутов, а отчасти — из инородцев, варваров-наемников, расквартированные внутри страны, стоявшие в городах в качестве гарнизонов, а также составлявшие действующую полевую армию. На рубеже VI–VII вв. было девять таких больших подразделений, включая две армии около Константинополя. Они вооружались и кормились от государства и под страхом высокого штрафа в фунт золота за каждого солдата их запрещалось использовать для иных, не военных работ. Сами воины, как указывал закон, должны были «потеть от обязанностей собственной службы», а не возделывать поля и искать работы в виде охраны домашнего скота или товаров.
В провинции, обычно в пограничном округе, командование провинциальными пограничными войсками возглавлял военный чиновник — дукс (по-гречески дука). Так называли того, кто имел должность заместителя претора. Дуки избирались императором чаще всего из числа дворцовой знати. Они обеспечивали защиту вверенных им районов, областей, краев, поступление налогов, выполняли полицейские функции. В 560-е гг. в Империи насчитывалось 25 таких командиров. Кроме того, полками командовали своеобразные генералы — стратиги, которые приносили присягу императору. Они должны были собирать и содержать собственные военные формирования, набирать офицерский состав, обеспечивать солдат оружием.
Общее военное командование поначалу было сосредоточено в руках двух или трех военных магистров — магистров милитум. Они набирались из числа кадровых военных. Один из них командовал пехотой (magister peditum), другой имел резиденцию в Константинополе, считался главнокомандующим и распоряжался кавалерией (magister equitum, греч. «каваллариа фемата»), роль которой повысилась к последней трети VI в. Тогда же, в связи с реорганизацией армии, к имевшимся магистрам добавились еще четверо региональных — в префектурах Восток, Иллирик (север Балканского полуострова), в диоцезе Фракия (около Константинополя) и в Армении, откуда можно было ожидать нападения персов. Позднее число военных магистров было доведено до восьми, а затем и до десяти, причем под их командованием оказались смешанные, и конные, и пешие войска.
В случае войны армия быстро собиралась под знамена императора, которому напрямую подчинялись магистры милитум, дуки, стратилаты — главнокомандующие в той или иной части Империи, стратиги и прочие командиры. Ее основу составляли расположенные в столице и ее окрестностях отряды отборных воинов императорской гвардии. Охрану царских дворцов несли палатины (от греческого слова палатий — дворец) — особые первоклассные, элитные части, похожие на гвардейские и набиравшиеся из храбрых, безжалостных варваров, преимущественно германцев. Эти придворные полки, числом семь, — по пол тысячи тяжелых кавалеристов в каждом, располагались прямо в Большом императорском дворце, где отныне постоянно пребывал император. При императоре Льве I (457–474 гг.) к ним добавилась отборная личная стража, всего из трехсот человек, которая тоже принимала участие в боях, пока в VII в. не приобрела чисто декоративное значение, как и палатинская гвардия.