Увеличением набора солдат из состава жителей империи — армян и исавров, фракийцев и македонцев — соотношение иностранных наемников в армии было значительно уменьшено. Это не только обеспечило большую преданность армии центральному правительству, но и способствовало восстановлению строгой дисциплины, чего невозможно было добиться при системе, когда личная популярность командующего покупалась ценой ослабления порядка. Была восстановлена старая система лагерей и полевых укреплений; новые армии Византии стали уделять окопным работам почти такое же внимание, как и легионеры Рима.
Основой византийской армии были тяжеловооруженные и облаченные в защитные доспехи конные лучники — катафракты. В их снаряжение входили стальной шлем с небольшим плюмажем, длинная защитная рубаха с нашитыми на нее металлическими пластинами или кольчуга, закрывавшие всадника от шеи до бедер; латные перчатки и стальные поножи. Поверх кольчуги часто надевалась накидка. Кони офицеров и рядовых первой шеренги в качестве защитного облачения несли на себе головной доспех и нагрудную броню. Каждый всадник был вооружен длинным копьем с флажком ниже наконечника (различные части имели плюмажи, накидки и флажки определенного цвета), луком с колчаном стрел, широким мечом и кинжалом. Позади седла была приторочена шерстяная накидка.
Теперь в армии использовались фигурные седла, вместо подкладок или одеял, закрепленных подпругой, как в предыдущие эпохи. Примерно в середине V века был сделан большой шаг в развитии конницы — стали употребляться стремена.
Можно с уверенностью сказать, что этот очень важный предмет конской сбруи удвоил эффективность действий всадника. Твердая, уверенная посадка в седле позволила в полной мере использовать ударную мощь конницы; теперь можно было эффективно применять длинное копье, да и пеший воин не мог больше так просто стащить всадника с коня, схватив его за ногу, — весьма важный фактор в гуще боя. Не совсем понятно, почему конница так долго не знала этого предмета снаряжения, но впервые стремена упомянуты в «Стратегиконе», хотя по некоторым фразам можно заключить, что ко времени написания этого трактата они уже были в ходу.
Воины легкой конницы не имели столь полного защитного снаряжения, но несли большой щит (которого у конных лучников не было). Вооружены же они были копьем и мечом.
Пехота также была двух видов. Тяжеловооруженные пехотинцы, скутаты, были облачены в стальной шлем с гребнем и короткую кольчугу и имели большой щит. Щиты эти, так же как и гребни на их шлемах, были окрашены в цвета полкового знамени. В качестве оружия они имели копье, меч и тяжелый боевой топор с острием на обухе.