Съществуват данни за следи от човешки живот в районите около град Яйце още от каменната ера. В околностите на града могат да се намерят останки от бронзовата и желязната епохи.
Първото споменаване на града датира от1386 г. и е свързано сХървое Вукчич Хърватинич, който през същата година е обявен заграф на града и получава титлатаконт ди Яйце.
През средновековието градът се развива и е сред най-големите селища на Босна и Херцеговина. През15 век е важен икономически център на региона, а в края на Босненската държава става седалище на босненските владетели. Тук е коронясан последният босненски кралСтефан Томашевич Котроманич и градът за две години е негова резиденция, а след обсадата от османците и падането на крепостта е екзекутиран тук през1463 г.
Яйце е бил кралски град от времето на управление наТвъртко II. Кралският дворец в града е споменат в исторически извори от1457 г., при царуването на кралСтефан Томаш.