סיפורו של הבניין מתחיל בשנת 1928. על מגרש שרכשה העירייה ושימש עד אז כפרדס הוקם צריף "בית תרומפלדור", ששימש כמועדון תנועת בית"ר בתל אביב. בשנת 1935 התקבל אישור לבניית בניין קבע במגרש, ושנה לאחר מכן נערכה תחרות אדריכלים סגורה שבמסגרתה הוגשו שמונה הצעות. בתחרות זכתה הצעתו של האדריכל הארי לוריא, הצריף נהרס והחלה הקמת הבניין החדש. ז'בוטינסקי אף נתן את הסכמתו שהבניין יישא את שמו. בשנת 1935 נערך שינוי נוסף באזור, שמו של הרחוב, שנקרא עד אז רחוב הכרמל (כי כאן עברה הדרך שקישרה בין יפו ובין הכרמל), שינה את שמו בקטע זה לרחוב המלך ג'ורג' החמישי, שציין באותה שנה את יום הולדתו ה-70.
הבניין שתכנן לוריא זכה לכינוי "מצודת זאב" משום שמועדון תנועת בית"ר, ששכן בו, כונה – "מעוז בית"ר" וגם כיוון שצורת הבניין הזכירה מצודה. הקמת הבניין ארכה כמה שנים ורק ב-1948 הושלמה הקומה השלישית. בשנת 1943 התיישב מנחם בגין בחדר בקומת המרתף, חדר המשמש כיום את מנהל המוזיאון. בחדר זה הקים בגין את המפקדה שלו וממנו יצאה הקריאה למרד בשלטון המנדט.
ב-1963 החליטה תנועת החירות להרחיב את המבנה הקיים. האדריכל לוריא נפטר ב-1953 ולכן נערכה תחרות אדריכלים חדשה שבה זכו משה בן-חורין ומרדכי בן-חורין. התוכנית הייתה להוסיף עוד ארבע קומות. מרדכי בן-חורין לא אהב את התוכנית שכן לדעתו בניין של 7 קומות היה נראה כמו גוש גדול בין כל הבתים. הוא הגיע למסקנה שבמקום להוסיף עוד כמה קומות, רצוי להקים מגדל. הרעיון הוצג לבגין שהסכים בשלושה תנאים: מסגרת התקציב תישמר, הקבלן שיגיש את ההצעה הזולה ביותר הוא שיזכה ולא משנה מה שיוכו הפוליטי, ולבסוף, לבניין לא תוכנס שום תוצרת גרמנית. וכך צמח מבנה שגובהו 60 מטרים ובו 16 קומות. בנייתו הסתיימה בשנת 1966.
המגדל נבנה על בסיס שלוש הקומות הקיימות שעברו הרחבה ושיפוץ. בניגוד למגדל שקירותיו החיצוניים עשויים בטון חשוף, הבניין עצמו צוּפה בשיש חברוני ונבנתה כניסה רחבה המשמשת את המוזיאון עד היום. מדרגות רחבות מכיוון הרחוב מובילות לאולם זיכרון שבסופו מעקה אשר ממנו אפשר להשקיף כלפי מטה על מוזיאון האצ"ל. לכל רוחב אולם הזיכרון נמתח פס שחור מאבני בזלת מלוטשות ועליו רשומים שמות כל חללי האצ"ל. קיר הזיכרון שבקצה האולם ויורד לכל הגובה עד למרתף, עשוי מבטון שחור ובמרכזו פסל ראש של זאב ז'בוטינסקי. יוסף קרמרמן, ממפקדי האצ"ל, בחר לשם כך את האומן יצחק דנציגר. את סורג הברזל בכניסה למוזיאון, מכיוון רחוב המלך ג'ורג', עיצב האומן הידוע משה שטרנשוס. מעל מכון ז'בוטינסקי נבנה אולם כנסים ואירועים כדי שיחזיק כלכלית את הבניין. באולם זה, "אולם העצמאות", הכריז בגין על ניצחון הליכוד בבחירות 1977.
משה בן-חורין החליט שקו המגדל לא ישיק לרחוב המלך ג'ורג' במקביל לקו של הבניין הקיים, אלא יעמוד בהטיה קטנה ויהיה משיק לסמטת שבע השקמים. מראש המגדל, מכיוון דרום ומכיוון צפון, יוצאים שני אלמנטים עיצוביים. בן-חורין, שרצה לקרוע חלונות בקומת הגג, חתך שני פסים בדגם הקרטון ומשך אותם כלפי מעלה. התוצאה מצאה חן בעיניו וכך נולדו שני גגות מעוצבים. בגין הודה לאדריכל שהצליח להכניס למגדל אלמנט שמזכיר את אלטלנה. בן-חורין נאלץ להודות כי אף שזה רעיון מוצלח, לא זו הייתה כוונתו.
אולם הישיבות של מרכז הליכוד, אולם האירועים וחדרו של בגין יושב ראש התנועה דאז, עוצבו
בלבנים אדומות. האדריכל בן-חורין רצה למחוק את הרעיון שאדום הוא סוציאליסטי וכחול הוא לאומי.
המגדל נבנה בסגנון ברוטליזם, מילה שקשה להיות אדיש כלפיה, ולא רק בגלל האדריכלות שהיא מייצגת, אלא בגלל השורש הלשוני הזהה למילה ברוטליות. אבל השם נובע מהמילה "ברוט" שמשמעו גולמי בצרפתית. הגולמי יכול להיות גס ובלתי מעובד, אך גם חשוף ופגיע.
מדובר באדריכלות שהתפתחה באירופה לאחר מלחמת העולם השנייה, ושמה לה למטרה להביע את החומרים, הסטרוקטורה והפונקציות של המבנה במבנה הסופי. באדריכלות זו רואים לבנים חשופות, בטון חשוף, קורות ועמודים, ואפילו צינורות ומערכות מיזוג אוויר חשופות.
האדריכלות הזו הולכת ונעלמת כי הציבור לא התלהב ממבנה חשוף. היא זכתה לעדנה בשנות השישים, השנים שבהן בנתה המדינה את מוסדות הציבור וזה מסביר מדוע רבים מבתי החולים, קופות החולים הגדולות, בתי המשפט, בתי העיריות והקמפוסים האוניברסיטאיים מצטיינים באדריכלות ברוטליסטית. כיוון שהיא אפיינה את הבנייה הציבורית, היא בלטה במיוחד בערי הפריפריה כמו נצרת עלית ובאר שבע, שהיוזמה הפרטית בהן הייתה מצומצמת. בית ז'בוטינסקי לא ניצב בודד מבחינה זו. מלון הילטון, בניין עיריית תל אביב, אצטדיון בלומפילד ובניינים נוספים נבנו בסגנון זה.
