Помимо экономических преобразований не забывалась и непосредственно военная реформа. К декабрю 1208 года были полностью укомплектованы личным составом оба батальона, численность которых составила по 1732 человека, а также артиллерийская рота, в которой было 24 новые тенсионные артиллерийские установки и 288 человек личного состава. Всего же регулярная армия Боспорского княжества составляла 3752 человека. В силу определённых обстоятельств укомплектовать армию доспехами и вооружением получилось только к маю 1209 года.
Каждая рота теперь имела не только свой номер, но и личный штандарт. Для управления боем введена новая должность – горнист, который приписывался в каждый батальон. Да, значительная часть армии ещё не прошла боевого крещения, но ветераны, бывшие с князем не одну кампанию, прикладывали все усилия в подготовке неофитов. Для этих целей раз в три месяца проходили недельные учения, в которых принимал участие весь личный состав армии. В остальное время шли регулярные тренировки и занятия по классам. Обучение велось по трём ключевым направлениям: физическая, психологическая и тактическая подготовка.
Для реализации первого направления был развёрнут большой спортивный комплекс, разместившийся в южном пригороде Боспора. В него входила масса разнообразных сооружений. Во-первых, небольшой стадион с пятью беговыми дорожками длиной порядка четырёхсот шагов. Во-вторых, бассейн с длиной сто шагов и шириной двадцать. В-третьих, крытый зал, в котором размещались тренажёрная площадка со штангами, турниками, брусьями и прочим инвентарём, а также спарринг-залы, в которых отрабатывался в первую очередь индивидуальный бой как с оружием, так и без него. Строевой бой осваивался на стадионе – на ровном поле внутри беговых дорожек. В-четвёртых, стрельбище для арбалетов и тенсионных артиллерийских орудий. В среднем в процессе подготовки бойцов каждому приходилось стрелять из арбалета не менее ста раз в неделю. А дружине – не менее двухсот. В-пятых, баня с парилкой и душевыми кабинами. Именно ими заканчивалась ежедневная тренировка. Помимо этого раз в неделю каждый из бойцов проходил курс массажа, который делали выкупленные из рабства китайцы. В общем, хороший уровень. Единственная серьёзная проблема была связана с рукопашным боем и фехтованием, так как никакого особого стиля не было, поэтому учились простым приёмам. В будущем нужно было найти нескольких человек из Индии или Китая и начать развивать собственную школу боевых искусств для повышения уровня индивидуальной подготовки бойцов.