Le College est d'abord apparu comme le Gonville Hall, fondé par Edmund Gonville, Recteur de la paroisse Terrington St Clement dans Norfolk en 1348, ce qui en fait chronologiquement le 4 collège de l'université. Lorsque Gonville mourut trois ans plus tard, il laissait une fondation pratiquement désargentée. Son exécuteur testamentaire, William Bateman, évêque de Norwich, fit transférer le collège sur le terrain attenant au collège que lui-même venait de fonder, Trinity Hall et, en l'installant dans de nouveaux locaux, le rebaptisa The Hall of the Annunciation of the Blessed Virgin Mary.
Le collège commençait sérieusement à tomber en ruine lorsqu'en 1557 un privilège royal pour la création d'un Gonville and Caius College fut accordé au médecin John Caius. Ce dernier, recteur du collège de 1559 à 1573, finança largement les réparations et accrut la surface des bâtiments.
Au cours de sa carrière de professeur, Caius dispensait les étudiants de le payer, mais en contrepartie leur imposait des règles peu ordinaires : il n'admettait aucun étudiant qui soit « contrefait, sourd, aveugle, muet, démembré, mutilé ou d'origine galloise ; qui souffre d'une maladie grave ou contagieuse, qui soit invalide ou sérieusement malade ». Caius demanda qu'on aménage une cour intérieure tripartite, Caius Court (« à moins que l'air, confiné dans un espace trop restreint, en devienne pestilentiel »). Quoi qu'il en soit, le recteur fit de son collège un centre réputé pour l'étude de la médecine, tradition que ses successeurs ont cherché à maintenir depuis.
