Քաղաքի պատմությունը սկսվում է նեոլիթի ժամանակաշրջանից, երբ այստեղ կար ձկնորսների և հողագործների բնակատեղի՝ Քիստրիկ անունով։ Գուդաութ անունը առաջացել է Գուդոու գետակի անվանից, որը հոսում է քաղաքի տարածքով։ Մեկ այլ տարբերակով՝ աբխազական լեգենդի համաձայն, հնում ապրել են պատանի Գուդան և Ութա օրիորդը։ Նրանք իրար շատ սիրում էին, սակայն չէին կարող միասին լինել իրենց ընտանիքների միջև թշնամության պատճառով։ Այդ իսկ պատճառով Գուդան իրեն գցում է գետը, որին հաջորդում է իր սիրելիի նմանատիպ արարքը։ 11-13-րդ դարերում քաղաքի մոտակայքում կառուցվել են բազմաթիվ ամրոցներ, դղյակներ և եկեղեցիներ։