As primeiras campanhas muçulmanas de ocupação da Península Ibérica decorreram entre 711 e 715 e Coimbra capitulou em 714. A sua topografia e situação geográfica contribuíram para o seu crescimento e desenvolvimento. Apesar de não ser uma cidade grande, no contexto geral do Al-Andaluz, era o maior aglomerado urbano a norte do Tejo. Tinha 10 hectares de recinto muralhado e entre 3000 a 5000 habitantes.
Da época islâmica perdurou a denominação dada ao interior da cidade intra-muros, a almedina, e extra-muros, o arrabalde. A localização da alcáçova, ou seja o palácio fortificado onde vivia o governador da cidade, foi também estabelecida durante a permanência islâmica na cidade. Esta construção será mais tarde o paço real, onde viveram os primeiros reis de Portugal.
A cidade foi reconquistada pelos cristãos definitivamente em 1064 por D. Fernando I, o Magno, ficando o governo da região entregue a D. Sesnando, que a reorganizou económica e administrativamente.