Według najnowszej hipotezy pierwotny Włocławek miał znajdować się na prawym brzegu Wisły i stanowił go zespół osadniczy z grodem w Zarzeczewie, którego geneza sięga pierwszej połowy XI w. Przeniesienie grodu na lewy brzeg Wisły nastąpić miało na przełomie XI i XII w. lub na początku XII w. Wzniesiono go na sztucznej wyspie otoczonej fosą. Prawdopodobnie w tym czasie na podgrodziu rozwinęła się osada typu wczesnomiejskiego, w granicach dzisiejszych ulic: Gdańskiej, Tumskiej, Łęgskiej, Towarowej i Bulwary.
Z wczesnym średniowieczem związane jest także osadnictwo w rejonie dzisiejszego Zawiśla. Badania archeologiczne ujawniły cmentarzysko z XI–XIII w. Na XII w. określany jest kościół św. Gotarda, który pełnił też rolę hospicjum. Od powstałego tam szpitala osadę zaczęto nazywać Szpetalem. W latach 1232–1236 ufundowane zostało opactwo cysterskie, które w zaledwie 10 lat później uległo zniszczeniu w wyniku najazdów pruskich.
Rola Włocławka wzrosła znacznie w pierwszej połowie XII w., kiedy utworzono w nim stolicę biskupstwa kujawsko-pomorskiego. W tym czasie, obok grodu, funkcjonowały dwa ośrodki wczesnomiejskie: książęcy i katedralny. Spowodowało to, że w jednym miejscu zostały skupione ważne funkcje administracyjno-państwowe (siedziba kasztelanii) i kościelne (ośrodek diecezji). Za rządów biskupa Michała Godziemby postawiono katedrę z ciosów kamiennych, usytuowaną w rejonie dzisiejszych ulic: Gdańskiej, Bednarskiej i Zamczej.
W połowie XIII w. rozpoczął się proces przechodzenia Włocławka spod władzy książęcej pod biskupią. Ostatecznie w 1266 r., książę Kazimierz Konradowic podpisał z biskupem Wolimirem układ, potwierdzony przywilejem, nadający prawo całkowitej własności Włocławka miejscowym biskupom. Siedziba kasztelanii została przeniesiona do Brześcia Kujawskiego, pomiędzy 1266 a 1275 r.
Rozwój ośrodka został gwałtownie przerwany przez wojnę polsko-krzyżacką. W 1329 r. Krzyżacy zajęli ziemię dobrzyńską, a następnie ruszyli z wyprawą na Kujawy. Działania wojenne doprowadziły do całkowitego zniszczenia Włocławka, kiedy to oddział krzyżacki – dowodzony przez Chrystiana von Köln – w niedzielę wielkanocną 23 kwietnia spalił miasto, zniszczył katedrę i wymordował lub uprowadził jego mieszkańców.
Starcie militarne pod Płowcami 27 września 1331 r. nie powstrzymało agresywnych poczynań krzyżackich. W 1332 r. oddziały zakonne opanowały zbrojnie terytorium Kujaw wraz ze wszystkimi ważniejszymi grodami. Wyjątkiem był Włocławek, który za zgodą Krzyżaków pozostał we władaniu biskupa Macieja Pałuki z Gołańczy. Kujawy znajdowały się pod okupacją Krzyżacką do Pokoju Kaliskiego w 1343 r.
Po zawarciu ugody z Krzyżakami biskup przystąpił do odbudowy miasta, połączonej ze znacznymi zmianami układu przestrzennego. Ich fundamentem był akt ponownej lokacji miasta, wystawiony przez biskupa Macieja Pałukę 8 września 1339 r. Dokument ten — oparty na prawie chełmińskim — określał ramy ustrojowe nowej gminy oraz relacje między mieszczanami a panem miasta.
W roku 1330 wybudowano kościół św. Witalisa, będący dziś najstarszym murowanym obiektem zabytkowym w mieście. W latach 1340–1411, na wzgórzu położonym w pobliżu rzeki Zgłowiączki, wzniesiono gotycką katedrę, która istnieje do dziś.
W latach Wielkiej Wojny z Zakonem Krzyżackim 1409–1411 we Włocławku działała jedna z central wywiadu królewskiego, zbierająca informacje z terenu państwa zakonnego, a rycerstwo kujawskie aktywnie uczestniczyło w bitwie pod Grunwaldem, rozegranej 15 lipca 1410 r.
Ostatni napad krzyżacki na miasto miał miejsce na początku września 1431 r. Oddziały zakonne doszczętnie je spaliły, nie oszczędzając przy tym mieszkańców i obiektów sakralnych. Zawarcie II pokoju toruńskiego 19 października 1466 r., który wieńczył zwycięsko wojnę trzynastoletnią, zdjęło z Włocławka odium sąsiedztwa krzyżackiego.
