Впрочем, нам мало известно о стратегии и тактике, которые использовались им в ходе этих войн. По крайней мере, его репутация непобедимого владыки, которой он пользовался на протяжении всех лет своего правления, создавалась не только за счет его личных качеств, но и благодаря созданной им военной организации, которая, формально основываясь на вассальной зависимости, приобрела специфический нормандский характер. С окончания смуты, которой ознаменовалось его малолетство, и вплоть до завоевания Англии Вильгельм методически создавал инструмент, уникальный по своей эффективности в тогдашней Европе. Подобно своим предшественникам, он имел личную гвардию, состоявшую из воинов, живших в его доме, но главной его заслугой было создание постоянного войска из рыцарей, которым он жаловал в качестве фьефа земли, конфискуемые у Ричардидов по мере одержания побед над ними. Тем самым он удерживал бедных рыцарей от намерения отправиться на поиски счастья в Италию, Византию или Испанию. Получив от герцога земельное пожалование, рыцарь должен был нести службу в его войске. Продолжительность этой службы составляла сорок дней в году, причем каждый вассал являлся на службу полностью экипированным за свой счет. Герцог мог продлить срок пребывания их на службе, беря на себя все расходы, начиная с сорок первого дня. На поле битвы войско подразделялось на боевые единицы по десять рыцарей с их пехотинцами; этими подразделениями командовали коннетабли.
Нормандскому войску были присущи все недостатки, характерные для любой армии того времени: постоянные трудности с продовольственным снабжением, крайнее несовершенство управления и сопряженная с этим неслаженность действий, даже если командование осуществлял энергичный и толковый полководец. Поэтому даже Вильгельм, умевший максимально эффективно использовать имевшиеся в его распоряжении средства, старался избегать так называемых сражений по всем правилам военного искусства. Зато он не чурался своего рода поединков между правителями, которые тогда практиковались государями и вдохновляли поэтов на сочинение эпических поэм; такому сражению предшествовала отправка к противнику пышно разодетого гонца, передававшего вызов, размахивая жезлом и правой перчаткой своего господина. Решительность Вильгельма как командира и его личный авторитет придавали нормандскому войску сплоченность и мобильность, довольно редкие для той эпохи. Его отряды пехотинцев, вооруженных луками, внушали ужас противнику. Оружием всадников в его войске служили меч и легкое копье, представлявшее собой двухметровое ясеневое древко с железным наконечником и предназначенное для метания.