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

עם הגעת העומאנים לזנזיבר ב-1698, הם החלו בביצורה של סטון טאון, והקימו את המבצר המכונה כיום "המבצר הישן", על חורבותיה של כנסייה. עם זאת, מעבר לביצורים, העיר לא התפתחה באופן משמעותי. רק בראשית המאה ה-19 החלה סטון טאון להתרחב, אם כי רוב בתיה החדשים היו בקתות קש, ולא בתי אבן. בשנת 1840 החליטו העומאנים להעביר את בירתם ממוסקט לסטון טאון, ובעיר החלה תנופת בנייה. למעשה, מרבית המבנים בסטון טאון נבנו החל מתקופה זו ועד סוף המאה ה-19. נוסף על השינוי הוויזואלי, חל בעיר גם שינוי דמוגרפי. עם הסולטאן הגיעו גם סוחרים ובעלי מטעים רבים, שזיהו את הפוטנציאל שבתבלינים שגודלו באי, ובמיוחד הציפורן. הסוחרים שהתיישבו בעיר הקימו לעצמם בתי אבן גדולים, המאופיינים בדלתות עץ מגולפות ומרפסות מקושטות.

ככל שהתרחבה העיר, גדלו גם ההכנסות ממסים, והסולטאן, סעיד בן סולטאן, החל בבניית מבנים ציבוריים שונים, כגון מסגדים ושווקים. בנו, ברע'ש בן סעיד, המשיך בתנופת הבנייה במחצית השנייה של המאה ה-19. בין היתר, הקים שני ארמונות - בית אל-סאהל, ששימש את סולטאני זנזיבר עד 1964, ובית אל-אָגָ'איבּ ("בית הפלאים"). כן הקים בעיר חמאם. פיתוח העיר דחק את התושבים הילידים של זנזיבר לפאתי העיר, מעבר לנחל הדָרָגָ'אני. אזור זה נקרא "נְגְ'אָמְבּוֹ" - "הצד האחר".

כשהגיעו הבריטים לזנזיבר, ב-1880, כבר היה רוב שטחה של העיר בנוי בצפיפות, ותוספות הבנייה שלהם היו בעיקר בשוליה. הבריטים הפכו את האזור הביצתי שבפאתיה הדרומיים לפארק, שסביבו הוקמו בנייני מגורים, קונסוליות, בתי חולים, בתי ספר ומוזיאונים. גשר הוקם מעל נחל הדרגא'ני, וקישר בין נג'אמבו לבין אזור השוק. עם השנים התמלא הנחל בפסולת, עד שב-1957 נסתם לגמרי. במקומו נסלל כביש (המכונה "Creek Road" - "דרך הנחל"), ומצידיו ניטעו גנים.

מורשתם העיקרית של הבריטים בסטון טאון הייתה הקמתו של נמל המים העמוקים בצפון העיר, ב-1925. בעקבות הקמת הנמל התפתח גם רובע מאלינדי, המשמש עד היום כמרכז התעשייתי של סטון טאון. עם המבנים החשובים הנוספים שהקימו הבריטים נמנים ה-State House ("בית המדינה", ששימש בעבר את המושל הבריטי, וכיום שוכנים בו משרדיו של נשיא זנזיבר), בית הדואר ובית המשפט.

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

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

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