Historici se v dnešní době nemohou shodnout, kdo jako první v Normandii nahlas vyslovil onu myšlenku na vpád do Anglie. Snad to byli někteří z blízkých Vilémových spojenců, spekuluje se o hraběti Robertovi z Mortain nebo hraběti Aimerym z Thouars, či snad vévoda sám. Každý si však musel uvědomovat, o jak náročný podnik se jedná.

Vilém ale rozhodně neponechával nic náhodě a hodlal se pojistit hned na několika frontách. Proto během krátké doby poté, co zjistil, že na anglický trůn už dosedl jiný kandidát, vyslal za papežem Alexandrem II. poselstvo, které díky podpoře biskupa Hildebranta (budoucího papeže Řehoře VII.), uspělo. Nebylo ani divu, neboť Římu už byl dlouho trnem v oku stav křesťanské obce v Anglii, která na něm byla značně nezávislá a ve které už řadu let působil jako arcibiskup z Canterbury exkomunikovaný Stigand. Papež mu pak jako souhlas s jeho záměrem poslal posvěcený praporec, který měl nést do bitvy.

Vilém začal otevřeně mluvit o válce na koncilu, který svolal do Lillebonne. Celý podnik ale nejprve musel překonat dva zásadní problémy. Zaprvé musel Vilém sehnat dost mužů, aby se mohl postavit Haroldově armádě, a za druhé – což bylo ještě obtížnější, zajistit pro své vojáky dopravu. Vévoda začal s obtížnějším úkolem a přikázal stavět plavidla. Zároveň s tím odeslal poselstva ke svým nejvýznamnějším vazalům a pod přísliby bohatství i výhružkami jim přikázal sehnat další.

Konstrukce jeho lodí je nám dnes neznámá, ačkoli se dá očekávat, že vycházela z vikingských kořenů. Měly tedy jediný stěžen z obdélníkovou plachtou a veslové kormidlo. Kolik jich nakonec měl Vilém není přesně známo, ale jejich počet se odhaduje na 500-600 (byť některé kroniky uvádějí až číslo 776). Stavba takového loďstva (byť část již byla jistě po ruce už dříve) zabrala mnoho měsíců a je až s podivem, že to bylo uskutečnitelné.

Čas, který musel naplnit čekáním na plavidla, věnoval vévoda shánění mužů do své armády. Velkou část jich získal od svých vazalů, které však musel zahrnout sliby, aby je donutil prodloužit feudálním systémem stanovenou lhůtu služby 40 dní za rok. Další přilákaní vidinou kořisti pak přišli z ostatních oblastí budoucí Francie – zejména z Bretaně a Flander. Vilém dále najímal žoldáky a do začátku léta se mu podařilo shromáždit snad až deset tisíc mužů.

Už počátkem srpna byla i jeho flotila připravena k vyplutí. Vilém chtěl vyrazit co nejdříve, protože jeho zem i finance tížilo vydržování jeho nové armády. Množství zásob, které musely každodenně proudit do vojenského tábora, muselo být skutečně ohromující. Štěstí mu však nepřálo, neboť nejprve mu přeplutí znemožňovalo počasí, a pak i Harold, který jej se svou flotilou blokoval. Až 12. září mohl konečně přeplout se svými loděmi do Saint-Valéry v ústí Sommy. Zde jej opět zdrželo počasí a zdálo se, že příprava přijde vniveč. Po dvou týdnech čekání však začal vát příznivý vítr a Vilém dal příkaz k urychlenému nalodění.

Flotila dorazila k anglickému pobřeží ráno 28. září a začala vplouvat do zálivu Pevensey. Z celého loďstva se ztratily pouhé dvě lodě, které se dostali do Old Romney, kde byly zajaty a jejich posádka pobita. Když Vilém udělal první krok po anglické zemi, údajně klopýtl a spadl na zem. Zdálo se to jako nešťastné znamení, ale blízký rytíř situaci zachránil a řekl, že vévoda už má vlastně anglickou zem ve svých rukou. Morálka mužů nebyla až tak vysoká, museli se obávat budoucích nebezpečí, které mohou číhat všude kolem, proto bylo třeba každou takovou špatnou předzvěst zadusit hned v počátku.

Obavy z napadení Anglosasy při vyloďování se ukázaly jako neopodstatněné. Po Haroldových bojovnících nebylo nikde ani vidu ani slechu, a tak mohlo vyloďování bez problémů pokračovat. Zátoka Pevensey však nebyla pro vyložení zásob a další výbavy zcela vhodná, a tak vévoda nechal lodě přeplout do nedalekého přístavu Hastings, poblíž kterého se rozhodl postavit svůj opěrný bod – dřevěnou pevnost – a čekat na Harolda.