אזרח ומחנך לאחר פרישתו מצה"ל עסק במשך כשנתיים במכירת מזגנים בניגריה וכשנה נוספת בניהול מפעל בנייה ברמלה. ב-1992 סיים את ניסיונו הקצר בעולם העסקים ושב לשירות ציבורי, הפעם במערכת החינוך, כמנהל בית הספר גימנסיה הרצליה בתל אביב. באותה עת סבל בית הספר מדימוי ציבורי ירוד, מתשתיות פגומות ומקשיים נוספים.
במהלך כהונתו כמנהל הגימנסיה הצליח חולדאי לשפר במידה ניכרת את מצבו של בית הספר וכך קנה לעצמו מוניטין של איש ביצוע יעיל ומחנך הדוגל במשמעת קפדנית. במסגרת תפקידו הוביל בין היתר שיפוץ של מבנה בית הספר ותשתיות אחרות. במקביל למצדדים בתוצאות אותן השיג כמנהל, נשמעו באותה עת גם לא מעט טענות מצד הורים ואנשי חינוך, כי חולדאי ניחן באישיות חמת מזג, מתנשאת וקצרת רוח, כי הוא מתקשה לקבל ביקורת והערות ולוקה בהתבטאויות בוטות ומעליבות. ביקורת באופי דומה ליוותה את חולדאי גם בשנים לאחר מכן בכהונותיו כראש עירייה.
ראש עיריית תל אביב-יפו ב-1995 התמודד חולדאי בבחירות המקדימות במפלגת העבודה, לקראת הבחירות לכנסת ה-14. בבחירות זכה בשיבוץ למקום ה-38, שהתברר כלא ריאלי שכן המפלגה זכתה ל-34 מנדטים בלבד.
ב-1998 הודיע חולדאי על התמודדות בבחירות לראשות עיריית תל אביב-יפו בראשות סיעה עצמאית בשם "תל אביב 1", מועמדותו נתמכה על-ידי מפלגת העבודה. במהלך הקמפיין הציג תוכניות שאפתניות להסדרת התחבורה בעיר, מתן פתרון למחסור בחניה וכן לשיפור איכות הסביבה. בבחירות עצמן ניצח את מועמד הליכוד לתפקיד דורון רובין בפער משמעותי של 25%.
בשנת 2003 נבחר חולדאי בשנית למשרת ראש העירייה כמעט ללא תחרות, לאחר שגבר על שאר המתמודדים שכללו את ארנון גלעדי, פאר ויסנר, גילה הרץ וישראל גודוביץ'. חולדאי זכה ב-63% מהקולות, כאשר המתמודד אחריו זכה ב-13% בלבד. לעומת זכייתו החד-משמעית בהתמודדות על ראשות העירייה, סיעתו "תל אביב 1" זכתה ב-4 מנדטים בלבד והייתה למפלגה השלישית בגודלה בתל אביב באותה מערכת בחירות.
בשנת 2008 נבחר חולדאי לכהונה שלישית עם 51% מהקולות. מתחרהו העיקרי, חבר הכנסת
דב חנין קיבל 34%. סיעתו, "תל אביב 1", הגדילה את כוחה במנדט ל-5 מנדטים, והייתה לסיעה הגדולה ביותר יחד עם "עיר לכולנו" של חנין.
חולדאי שב וניצח בבחירות שנערכות בשנת 2013 לאחר שזכה ב-53% מהקולות, מול 38% בלבד מהקולות בהם זכה יריבו העיקרי איש התקשורת ניצן הורוביץ קיבל 38%. סיעתו, "תל אביב 1", שמרה על כוחה (5 מנדטים), והייתה לסיעה השנייה בגודלה, אחרי סיעת מרצ.
הערכת כהונתו כאמור לעיל, חולדאי מאכלס את לשכת ראש עיריית ת"א במשך קרוב ל-20 שנים. במהלך שנים אלו קידם והוביל מדיניות אחידה במרבית תחומי החיים בעיר. קווי המדיניות שהתווה חולדאי ולא פחות מכך, יכולת הביצוע המרשימה של מדיניות זו, הקנו לו הערכה לא מבוטלת בזכותה ניצח שוב ושוב בבחירות לראשות העיר. עם זאת, במידה לא פחותה אותה מדיניות הפכה אותו מושא לביקורת עזה. להלן כמה מן הדגשים העיקריים המאפיינים את פעילותו כראש עיריית תל אביב-יפו:
חידוש תשתיות - אחד הסממנים המזוהים ביותר עם כהונתו של חולדאי הוא ההשקעה הניכרת והמתמשכת בחידוש ושדרוג התשתיות בעיר. במהלך שנותיו בתפקיד חלק ניכר מן הרחובות במרכז העיר ובצפונה עברו חידוש יסודי, תוך מתן דגש על טיפוח נוי, הוספת מתקנים שונים לנוחות התושבים, סלילת שבילי אופניים, תיקון בלאי וכדומה. במסגרת זו ניתן דגש מיוחד לשדרות ולרחובות המרכזיים בעיר בהם: רחוב אבן גבירול, שדרות רוטשילד, שדרות בן-גוריון, שדרות ירושלים, רחוב דיזנגוף, שדרות ח"ן ועוד. מאמץ דומה הושקע בפיתוח וחידוש מתחמי בילוי ופנאי מרכזיים דוגמת: הארכת הטיילת מחוף הים בהרצליה ועד לחוף בת ים, נמל תל אביב, נמל יפו, מתחם התחנה, מדרון יפו, מתחם הבימה, חידוש כיכר דיזנגוף ועוד.
לצד הביקורת שהועלתה לא פעם בשל חוסר נוחות שנגרם לתושבים בשל עבודות התשתית, הושמעו לא פעם טענות כי קיים פער משמעותי בין התקציבים המושקעים בתשתיות באזורי מגוריהן של האוכלוסיות החזקות בעיר (בעיקר צפון העיר ומרכזה) אל מול התקציבים המושקעים בפיתוח ותיקון תשתיות בשכונות בהן מתגוררת אוכלוסיות חלשות (בעיקר דרום העיר, חלקה המזרחי ויפו).
מגדלים ומשבר מחירי הדירות - היקף השטחים הפנויים לבנייה בתל אביב הוא מצומצם ביותר, על כן עיקר הבנייה בה מבוססת על חידוש או בנייה מחדש של שטחים בנויים או פינוי והכשרת שטחים תפוסים (דוגמת פינוי שדה דב, פינוי מבנים בבסיס הקריה וכו'). למרות קושי יסודי זה הצליח חולדאי לקדם מספר לא מבוטל של מיזמי מגורים, משרדים ומסחר ברחבי העיר.
בהכללה ניתן לומר כי בהתייחס לשטחי משרדים ומסחר השטחים הבנויים בעיר נותנים מענה סביר, תמונה אחרת לגמרי מתקיימת בתחום הבנייה למגורים. במהלך שנותיו בתפקיד הוביל חולדאי מדיניות תכנון ובנייה אשר נתנה עדיפות ואישרה את הקמתם של מגדלי דירות רבי-קומות יוקרתיים. אומנם כי גם טרום כהונתו של חולדאי מחירי הדיור בתל אביב היו גבוהים ביחס לממוצע הארצי, אולם העלייה הדרמטית במחירי הדירות ומחיר הקרקעות בישראל בשנים האחרונות, הביאה לכך שמחירי הדירות בת"א יצאו מהישג ידן של מרבית המשפחות בישראל. יתר על כן, עליית מחירי הדירות באה לידי ביטוי גם בעלייה דרמטית במחירי השכירות למגורים בעיר, בירידה במספר הדירות המוצעות להשכרה במחירים נגישים למעמד הביניים ובשבירת איזון יחסי הכוחות בין השוכרים למשכירים באופן המביא לא פעם לניצול השוכרים.
השילוב בין משבר הדירות, הופעתם של משקיעים זרים בשוק הנדל"ן ומדיניות התכנון שהוביל חולדאי הביא לכך שרובה המכריע של הבנייה למגורים לתל אביב נעשתה במגדלי דירות המכוונים לעשירון העליון ונושאים תגי מחיר בין כמה מיליוני עד עשרות ומאות מיליוני שקלים. בין מיזמי נדל"ן אלה ניתן למנות את: פארק צמרת, מגדל פרישמן, מגדלי המגורים במתחם הקריה, מגדלי צמרת ברחוב פנקס, מגדל השופטים, מגדלי גינדי במתחם השוק הסיטונאי ועוד.
מדיניות התכנון והבנייה שהוביל חולדאי הולידה נגדו ביקורת כי מדיניותו הופכת את תל אביב בפועל לעיר לעשירים בלבד והודפת החוצה את האוכלוסייה הצעירה ואת משפחות מעמד הביניים והמעמד הנמוך. על-רקע ביקורת זו, קידם חולדאי מספר יוזמות לבניית דיור בר-השגה בדרום ומזרח העיר, אולם היקפן של אלה מצומצם ביותר. בנוסף יש לציין כי גם תוכניות פיתוח ובנייה עתידיות שמקדמת העירייה מתאפיינות באותם מגדלי יוקרה, דוגמת תוכנית לבנייה בכיכר אתרים, התוכנית לבנייה בשדה דב ובשטחים נוספים בצפון-מערב העיר. בהקשר זה יש לציין כי הכנסות העיירה מפעילות הנדל"ן בה תרמו במידה משמעותית להצלחתו של חולדאי בכיסוי הגרעון התקציבי שירש מקודמיו ובניהולה של העיר באופן מאוזן תקציבית.
ביקורת נוספת המושמעת נגד מדיניות התכנון והבנייה של חולדאי נוגעת להקמתם של מגדלי ענק באופן המשבש את האופי התכנוני בסביבתם, פוגע בערכי נוף ומונע שימוש חופשי בשטחים ציבוריים. שתי דוגמאות בולטות בהקשר זה הן: מגדל נווה צדק ומגדל אסותא, סביב הקמתם ניהלו תושבי הסביבה מאבק ציבורי.
תרבות, ספורט ופנאי - אחד ההישגים המשמעותיים המקושרים לכהונתו של חולדאי הוא פיתוח וקידום פעילות התרבות, הבידור והפנאי בתל אביב, מדיניות אשר סימנה המזוהה הוא מיתוג העיר כ"עיר ללא הפסקה".
השקעה מתמשכת במוסדות תרבות, אירועי תרבות, ספורט ובידור (לדוגמא: לילה לבן, מרוץ לילה ועוד), שימור מבנים בעלי ערך אדריכלי, קידום ערכים ליברליים (דוגמת עידוד תרבות גאה וכדומה) ופעילויות דומות הביאו לקידום וביסוס מעמדה של תל אביב כבירתה התרבותית של מדינת ישראל. לא פחות מכך נחשבת תל אביב למוקד תרבות הזוכה להכרה בינלאומית ומושך אליו מבקרים ותיירים מרחבי העולם. מעמד זה הוא בעל תרומה משמעותית לעסקים בעיר, ליצירת מקומות תעסוקה ולתקציבה של העירייה עצמה.
תחבורה - בתחום זה ההערכה המקובלת היא כי בשנות כהונתו טרם הצליח חולדאי לרשום הישגים משמעותיים, ובעיות היסוד המלוות את חיי התושבים ממשיכות להתקיים: מחסור במקומות חנייה, היעדרה של תחבורה ציבורית יעילה ועוד. המיזם המשמעותי בתחום זה הוא מיזם הרכבת הקלה (מיזם ממשלתי) הנמצא בהקמה וצפוי להתחיל בפעולתו בעוד מספר שנים. בין פעולותיו של חולדאי בתחום התחבורה ניתן למנות את ההשקעה בפיתוח שבילי אופניים, מיזם תל-אופן (השכרת אופניים לתושבים) ופרויקט עתידי דומה להשכרת כלי רכב. פיתוח שבילי האופניים הוליד גם הוא ביקורת נגד חולדאי סביב העירוב המסוכן בין הולכי רגל לרוכבי אופניים על מדרכות העיר.