Stavanger er også en av Norges aller eldste byer. Den vokste fram på 1100-tallet i en periode preget av folkevekst og økende urbanisering over hele Nord-Europa. De arkeologiske og historiske kildene er sparsommelige. Derfor er det mye vi ennå ikke vet om den første bydannelsen. Heller ikke bynavnet har vi noen sikker forklaring på, men det består av to deler: staf og angr. Staven er trolig den bratte vestsiden av Valberget som i sin tid sto som et landemerke i det sentrale havnebassenget Vågen. Og angr var selve bukta, vika eller Vågen.
Kongemakten og kirken trengte et sterkt fotfeste på Sørvestlandet. Stavanger hadde en naturlig havn og lå strategisk til, like ved skipsleia langs kysten. I 1120-årene ble det opprettet et bispesete her. Den første biskopen kom fra England. Samtidig startet byggingen av katedralen. Den ble opprinnelig reist som en romansk basilika i anglo-normannisk stil. Bispesetet og katedralen i Stavanger ble et av knutepunktene i det nasjonale maktapparatet. Etableringen av disse institusjonene ligger til grunn for at byens grunnleggelse offisielt dateres til året 1125.