Na het vertrek van de Romeinen uit Utrecht gebruikte de burgerbevolking de gebouwen van het Romeinse legerkamp als onderkomen. Uit deze tijd zijn op het Pieterskerkhof enkele graven met giften gevonden. Op het Domplein is een kam gevonden uit de vijfde of zesde eeuw. Veel vroegmiddeleeuwse sporen zijn helaas uitgewist door de overstromingen die Utrecht in de twaalfde eeuw troffen. Utrecht was in deze tijd waarschijnlijk in handen van de Friezen.
In Noord-Frankrijk en België waren het de Franken die na de Romeinse periode de macht hadden overgenomen. Aan het einde van de vijfde eeuw breidde de Frankische koning Clovis zijn rijk flink uit. Clovis was de kleinzoon van koning Merovech. Zijn nazaten worden daarom aangeduid als de Merovingers. Eén van Clovis' nazaten en opvolgers, koning Dagobert, herbouwde rond 630 de Maartenskerk, die al enkele decennia daarvoor in Utrecht gebouwd was. Hij droeg de kerk over aan bisschop Kunibert van Keulen met de opdracht om vanuit Utrecht zendingswerk onder de Friezen te gaan verrichten.
Dat had weinig succes. Twintig jaar later werd Utrecht ingenomen door de Friezen en werd de Maartenskerk opnieuw verwoest. Mogelijk fungeerde Utrecht toen als de residentie van de Friese koning. Hofmeier Pippijn II van Herstal trok in 690 tegen de Friese koning Radbod ten strijde en veroverde een deel van het gebied van de Friezen. In 695 versloeg Pippijn koning Radbod in een gevecht bij het voormalige Romeinse legerkamp bij Wijk bij Duurstede. Toch was de macht van Radbod nog niet gebroken. Na de dood van Pippijn kwam Radbod weer in opstand en zijn plundertocht door het Frankische rijk duurde tot zijn dood in 719. Pas daarna wist Karel Martel, de zoon en opvolger van Pippijn, de macht van de Friezen te breken. Utrecht was nu voorgoed in handen van de Franken en werd het centrum voor de kerstening van de noordelijke Nederlanden.