Si l'archéologie permet petit à petit d'apporter quelques connaissances sur la ville du Moyen-Age, l'histoire n'apporte des documents qu'à partir du XIe siècle et en 1235 la Vie de saint Corentin attribue la fondation de la ville au roi Gradlon vers les Ve ou VIe siècles. Gradlon, roi de la ville d'Ys, aurait alors fait don de son « château » situé au confluent de l'Odet à l'ermite Corentin pour y édifier sa cathédrale.

De ce récit légendaire on peut néanmoins retenir plusieurs éléments constitutifs de la ville. Tout d'abord le choix du site, le confluent (Kemper en breton) qui laisse son nom à la ville, associé à celui de Corentin, qui lui donne sa vocation épiscopale. Historiquement, il est probable que la fondation de l'évêché se situerait plutôt à l'époque carolingienne, date à laquelle on connaît un Gradlon qui aurait pu servir de modèle pour celui de la légende. En 1235, la place de la cathédrale porte le nom de « Tour du Chastel » ce qui pourrait correspondre à une première enceinte dont on peut aisément retrouver trace. Naturellement limitée au sud par l'Odet, elle ouvrait par deux portes à l'ouest, une rue du Guéodet encore en place à la fin du 19ème siècle et l'autre rue Kéréon dont le nom « Porz Men », la porte en pierre, apparaît régulièrement qui pouvait se situer soit au niveau de la rue des boucheries où la maison datée de 1552 conserve toujours une statue dédiée à Notre-Dame des Portes, soit au niveau du rétrécissement de la rue. A l'est, la rue des Réguaires (rac-kaer, devant la forteresse) donne une indication toponymique sur le tracé qui pouvait suivre le cours du Frout, tandis qu'au nord le tracé actuel de la rue Verdelet apparaît comme une limite vraisemblable.

Si on s'accorde sur le lien entre création de la ville, arrivée des immigrants bretons et diffusion du christianisme entre Ve et VIIIe siècles, la présence d'un évêché à Quimper n'est attestée qu'au IXe siècle. Les études récentes attribuent l'évangélisation de la Cornouaille à un moine, saint Tugdual, qui aurait été à l'origine de la création d'un monastère à l'emplacement de la cité gallo-romaine (Locmaria). La présence ancienne à Locmaria d'une chapelle dédiée à saint Colomban confirme l'usage du rite scottique avant l'adoption à l'époque carolingienne de la règle bénédictine par les abbayes bretonnes. Par ailleurs, l'usage de faire passer le nouvel évêque de Cornouaille par Locmaria avant son entrée dans la cathédrale lors des cérémonies de son intronisation, pose la question d'un évêché primitif à Locmaria avant l'adoption du site du confluent.

Mis à part un chapiteau roman trouvé dans les fondations d'une maison de la rue des Réguaires en 1879, on ne sait pratiquement rien des édifices qui ont précédé la cathédrale gothique. Cependant, à partir de la fin du Xe siècle, les actes concernant la famille comtale de Cornouaille montrent qu'elle possède le pouvoir comtal et épiscopal transmis héréditairement. Au début du XIe siècle le comte-évêque Benoit transmet ses pouvoirs à deux de ses fils, Alain Canhiart devient comte de Cornouaille, tandis qu'Orscant prend le titre d'évêque. La vie d'Alain Canhiart (mort en 1058) nous donne quelques renseignements sur la ville à cette époque. On sait ainsi que le monastère de Locmaria est passé sous le giron du comte et qu'il abrite une communauté de femmes dont l'abbesse est Hodierne, fille d'Alain Canhiart. On retiendra aussi de cette partition des pouvoirs, une partition du sol qui sera décisive dans l'évolution ultérieure de la ville (ville de l'évêque, terre-au-Duc) dont les conséquences se feront sentir jusqu'au XIXe siècle. A sa mort, Alain Canhiart choisit de se faire inhumer dans une chapelle Notre-Dame de la Victoire, proche de la cathédrale , qu'on s'accorde à identifier comme la chapelle absidale intégrée à la cathédrale lors de la construction du chœur gothique. Les nombreuses fondations religieuses du comte de Cornouaille (Quimperlé, Locronan) témoignent de la puissance qu'il va léguer à son fils Hoël qui monte sur le trône ducal en épousant Havoise, héritière de son frère Conan II mort en 1066. Là encore, les conséquences seront importantes pour l'avenir. Les ducs de Bretagne, par souci dynastique, notamment au 15ème siècle, multiplieront les actes et fondations au profit de la cathédrale.

Le roi Gradlon

Personnage légendaire, sans doute inspiré d'une part de vérité historique, le roi Gradlon est une figure incontournable de la Cornouaille. Roi de la ville d'Ys, ami de saint Guénolé et de saint Corentin, Gradlon figure à cheval entre les deux flèches de la cathédrale depuis le 15ème siècle, tandis que la dalle funéraire de Gradlon de Kervastard (1383) rappelle la notoriété de ce prénom dans la société médiévale.
Le personnage du roi Gradlon apparaît vers 880 dans le second livre de la Vie latine de saint Guénolé de l'abbé de Landévennec, Wrdisten. La légende de gradlon s'amplifie après les invasions barbares du 10ème siècle jusqu'à devenir le héros d'un lai breton et l'un des personnages d'une chanson de geste.
Mais la célébrité de la ville d'Ys est due surtout aux écrivains du 19ème siècle qui ont rédigé et enrichi la légende avec de nombreuses variantes. En 1845, Théodore Hersart de la Villemarqué l'intègre dans son recueil des chants de la Bretagne Le Barzaz Breiz et Emile Souvestre en donne une version dans le Foyer breton en 1844. En 1850, Olivier Souvestre est l'auteur de la chanson Ar Roue Gralon ha Kear Ys qui fut un des principaux supports de sa diffusion.

Gradlon régnait jadis sur la Cornouaille entouré de deux saints qui le conseillaient, le moine Guénolé et l'ermite Corentin dont il avait fait son évêque en lui donnant son château de Quimper. Le roi avait une fille, Dahut, belle bien entendu, pour la quelle il avait fait construire une ville magnifique : la ville d'Ys. Cette ville, située sur la baie de Douarnenez était protégée de la mer par des digues et des écluses dont le roi gardait la clé. Dahut y menait une vie de douceurs et de plaisirs. Un jour, sur la digue, elle rencontre un séduisant chevalier qui la convainc de dérober les clés que son père conserve autour du cou. Profitant du sommeil du roi elle s'en empare et les remet au chevalier rouge qui n'est autre que le Diable... Celui-ci ouvre alors les écluses et la ville est envahie par les flots. Seuls Gradlon monté sur son cheval Morvac'h et Guénolé réussissent à s'échapper, non sans que saint Guénolé n'ait convaincu d'abandonner Dahut à la mer. Noyée, celle-ci se changea, dit-on, en une sirène, Morgane, qui s'acharne toujours à perdre les marins...