Volgens oude Friese legendes is Hoorn gesticht door Hornus, stiefzoon van koning Radbod. Hornus was getrouwd met Gunterdom, dochter van Gordianus, stadhouder van Teckenburgh. Hij stichtte volgens de legendes in 716 in het westen van Friesland aan het water een plaats en noemde die naar zichzelf. Dit was onder de Friese adel vrij gebruikelijk. Dezelfde legendes vertellen ook dat het plaatsje al in 724 afbrandde, en dat het toen jaren duurde voor het herbouwd werd. Voor zover deze legende al klopt, hoeft dit Hoorn niet op de huidige plaats gelegen te hebben, maar wellicht in het gebied dat later door de Zuiderzee overspoeld is. Het verplaatsen van plaatsen die dreigden te overstromen was in de middeleeuwen in West-Friesland gangbaar. Van Enkhuizen, Scharwoude, Etersheim en Warder is bekend dat zij in westelijke richting verplaatst zijn door de oprukkende Zuiderzee. Oosthuizen is daarentegen door de groter wordende Beemster in oostelijke richting verplaatst. De grens van de Zuiderzee aan de Westfriese/Waterlandse zijde lag rond 600 veel oostelijker (van Wijdenes richting Volendam en Marken), maar is na verscheidene overstromingen van veengebieden kilometers opgeschoven. Met name na 1100 vonden er steeds heftigere overstromingen plaats.
De oudste bewonersrestanten die tot nu toe bij archeologische opgravingen gevonden zijn, stammen uit circa 1200. Hoorn was toen niet meer dan een kleine plaats, met boerderijen en wellicht enige handel. Volgens de Hoornse geschiedschrijver Velius ontstond Hoorn in de 14e eeuw bij de monding van de Gouw (eigenlijk De Tocht geheten; de Gouw was de weg en buurtschap erlangs) voorbij de dijk van het Oost en het West, een veenstroompje dat via een sluis en overtoom bij de Rode Steen in de Zuiderzee uitmondde. Ook de landweg Noord (in feite de scheidingsdijk tussen Ooster- en Westerpolder, het verlengde van het Keern en Rijsdam) kwam hier uit. Op dit centrale punt zouden Hamburgse broers in 1316 hun pakhuizen en een herberg gebouwd hebben. Dit laatste kan waar zijn, maar volgens de opgravingen bestond Hoorn toen al, en Hoorn wordt ook al eerder in geschriften genoemd. Bovendien is de binnendijk van Rijsdam-Keern-Noord vermoedelijk in 1320 aangelegd. Tot dan lag de waterkundige bangrens tussen de onginningsgebieden Hoorn (later deel van de Oosterpolder) en Berkhout (later deel van de Westerpolder) in de Keernsloot. De sluis van de Rode Steen bestond toen al wel enkele decennia (1288).
