על פי המסורת שם העיר נולד כתוצאה ממערכה שניהל הקיסר יסחק הראשון נגד היהודים של ווגרה במאה ה-15 כאשר חייליו קיבלו פקודה ללון קרוב אליו מחשש להתקפה מכאן גון=צד ו-דר=ללון גונדר[1]

עד המאה ה-16 לא ייסדו קיסרי השושלת הסולומונית בירה קבועה, אלא חיו חיי נוודות ונדדו ממקום למקום. כך, תוך דיכוי בלתי פוסק של מורדים, אכפו את שלטונם, גבו מיסים, קיימו משפט והקימו כנסיות, וסיפקו את מזון החיילים ישירות מהאזורים אליהם הגיעו. במחצית השנייה של המאה ה-16 החלו השליטים האתיופים להתמקד באזור אגם טאנה. בתחילה הקימו יישובי אוהלים שלעיתים קרובות שבו וקמו באותו מקום, אך לא ייסדו יישוב קבע. עם יישובי אוהלים אלה נמנים אמפראז, איבה, גורגורה ודנקז. לאחר מכן החלו מקימים טירות במקומות אלה.

בגונדר שכן באותה עת כפר קטן וחסר ייחוד, והמבנה המשמעותי היחיד ששכן בו היה כנסייה קטנה שהקים הקיסר סוסניוס בתחילת המאה ה-17, ואשר הוקדשה לקדוש תקלה היימנות. העיר נוסדה על ידי הקיסר פאסילידס, זמן קצר לאחר מכן, בשנת 1635 או 1636, והתפתחה למרכז חקלאי ולעיירת שוק. לפי המסורת הוליך תאו את הקיסר פאסילידס לבריכה על-יד היישוב הארעי "אנגאראב", מקום בו ישב נזיר שאמר לקיסר ששם יקים את בירת ממלכתו. פאסילידס בנה את טירתו באותו האתר וייסד בכך את המתחם המלכותי פאסיל גמב, ששימש את קיסרי אתיופיה ב-220 השנים שלאחר מכן[2]. עוד הקים הקיסר בגונדר שבע כנסיות ואת מרחצאות פאסילידס. שתי הכנסיות הראשונות, "פיט מיכאל" ו"פיט אבו", נבנו על-מנת לסיים מגיפות. חמשת הקיסרים ששלטו אחריו בנו גם הם את ארמונותיהם בפאסיל גמב והוסיפו מבנים רבים במתחם ובעיר.

כתוצאה מהחלטת מועצת הכנסייה ב-1668, הפריד הקיסר יוהנס הראשון את תושבי העיר לפי השתייכותם הדתית. מהלך זה הביא תוך שנתיים להקמת הרובע המוסלמי בעיר, שנקרא "יסלאמגיה" (באמהרית "מקום האסלאם" או "ארץ האסלאם") או "אסלאם בית" ("בית האסלאם"). הרובע מוכר כיום בשם "אדיס עָאלֶם" ("עולם חדש")[3].

במאה ה-17 הוערכה אוכלוסיית העיר בכ-60,000 תושבים, וב-1678 ביקר הבישוף הארמני הוואנאס בעיר וציין שהיא "גדולה פי שניים מאיסטנבול". רבים מהבניינים שנבנו בתקופה זו שרדו אף על פי שהמאה ה-18 הייתה תקופה של מהומות בעיר. בתקופת מלכותו של הקיסר ייאסו הגדול, צברה גונדר כוח בתוך האימפריה האתיופית, וכאשר הקיסר קרא לתושבים להצטרף למערכה כנגד ממלכת דמות בדרום גוג'ם, תושביה סירבו והוא נטש את תוכניתו[4].

העיר שימשה כבירת אתיופיה עד שהקיסר תוודרוס השני העביר את הבירה הקיסרית לעיר דברה תבור בה הוכתר ב-1855. ב-1864 וב-1866 בזז תוודרוס השני את כנסיות גונדר באופן שיטתי, ורוקן אותן מאוצרותיהן וספריהן. לבסוף הוא גרש את תושבי העיר והעלה אותה באש. הקיסר הבא תקלה גיורגיס השני, אשר מלך משך ארבע שנים, בין 1868-1872, תיקן מעט מהנזקים שגרם קודמו, וסיפק משאבים לשיפוץ ההרס[5], אך העיר הותקפה שוב ב-1888, הפעם על ידי צבא המהדייה, והמעט שנותר ממנה, בייחוד הכנסיות (42 מתוך 44)‏[6], חרב. אולם מבני האבן העיקריים בפאסיל גמב שרדו גם הפעם.

לאחר כיבוש אתיופיה בידי איטליה ב-1936, המשיכה גונדר להתפתח תחת שלטונה[7]. בזמן מלחמת העולם השנייה, נותרה בגונדר העמדה האחרונה של הכוחות האיטלקיים, ובנובמבר 1941 הופצצה והוכנעה על ידי הצבא הבריטי, שישה חודשים לאחר שאדיס אבבה נכבשה. אזור גונדר היה אחד ממרכזי הגרילה האיטלקית כנגד הכוחות הבריטיים עד קיץ 1943‏[8].

בתקופת מלחמת האזרחים האתיופית, הצליחו כוחות האיחוד הדמוקרטי האתיופי להשתלט על חלקים גדולים מבגמדר, ובמהלך 1977 פעלו במרחק נגיעה מגונדר, נכונים לכבוש את העיר[9]. כחלק ממבצע תוודרוס לקראת סוף מלחמת האזרחים, נכבשה גונדר על ידי החזית העממית לשחרור תיגראי במרץ 1991‏[10].