זמן קצר אחרי שצביקה שרף הבהיר לדני חלוץ כי לא יאמן את נבחרת ישראל, הפור נפל: הוועדה המקצועית של איגוד הכדורסל המליצה היום (חמישי) פה אחד על ארז אדלשטיין, מאמן הפועל תל אביב, לתפקיד החשוב ביותר בענף, והמינוי יובא לאישור האיגוד כבר ביום רביעי. אדלשטיין ישתכר כ-200 אלף שקלים על פני תקופה של שלושה חודשים - קמפיין המוקדמות עצמו. "אני מקווה שזה ייצא לפועל, אבל לא נקדים את המאוחר. אני אשמח מאוד שזה יקרה".
כאמור, שרף הודיע מוקדם יותר ליו"ר האיגוד כי הוא מסיר את מועמדותו לתפקיד מאמן הנבחרת, זאת מכיוון שהוא לא מעוניין לפרוש מתפקידו בסיעת "עוז". אדלשטיין היה מועמד מוביל עוד קודם לכן, אבל הודעה זו של מאמן מכבי ראשון לציון סללה את דרכו של "הג'ינג'י" למשרה החשובה.
ארז אדלשטיין החל את דרכו כעוזר מאמן בהפועל גבת בשנת 1991 ובהמשך הפך למאמן הראשי שלה. בעונת 1995/96 הגיע בפעם הראשונה למלחה, כעוזרו של פיני גרשון. השניים היו שותפים להישג הראשון של הירושלמים, כאשר ניצחו 65:67 את מכבי ת"א בגמר הגביע מסל הניצחון המפורסם של עדי גורדון.
אדלשטיין הפך לראשונה כמאמן ראשי בעונת 1998/9, כאשר קיבל את המפתחות לעמוד על הקווים של בני הרצליה. אדלשטיין הדריך את המועדון במשך שתי עונות רצופות ורשם 18 ניצחונות ו-26 הפסדים. לאחר מכן עבד המאמן בהפועל גליל עליון במשך שנתיים ורשם עונה אחת נוספת במכבי ר"ג. בעונת 2002/3 אדלשטיין חזר למלחה, אך לאחר שרשם 5 הפסדים ב-8 משחקים הוחלף על ידי גדי קידר ומונה למאמן לראשונה למאמן הפועל תל אביב.
הרומן של אדלשטיין והאדומים נמשך גם בעונה שלאחר מכן, 2003/04, שהייתה שנת שיא עבור המועדון, שהגיע אז לפיינל פור של היורופליג ורשם ניצחון מדהים 71:96 באוסישקין על מכבי. ב-2005/06 הוא הדריך את הפועל י-ם בעונה הראשונה תחת ארקדי גאידמק. אדלשטיין נכנע למכבי ת"א 96:66 בגמר הפיינל פור, הפסיד בגמר הגביע ונעצר רק בחצי גמר היול"ב קאפ. לאחר מכן אדלשטיין עזב את ליגת העל ועבד כעוזרו של פיני גרשון באולימפיאקוס ובהמשך כעוזר מאמן בנבחרת ישראל. בתחילת עונת 2011/12 אדלשטיין מונה למאמן הפועל ת"א פעם נוספת, החזיר אותה לליגת העל והוביל אותה לפלייאוף בעונה שעברה. בסך הכל אימן אדלשטיין ב-260 משחקי ליגה בקריירה, כאשר מתוכם ניצח ב-147 משחקים ורשם 113 הפסדים.
