בגיל 26 חזר גרשטיין לישראל והחל ללמד ב"בצלאל". תחילה לימד רישום, ואחר-כך הצטרף לסגל המחלקה לצורפות, אשר עברה בתקופה זו תהליך התחדשות בניהולו של אריה אופיר. באותה תקופה עברה המחלקה מצורפות בסגנון מיושן המושפע מסגנון "בצלאל" המסורתי, לעבר תפישות חדשניות שהושפעו מאמנות מודרנית כללית. כבעל רקע באמנות ולא בצורפות, היה גרשטיין אחראי בשנים אלו על קירוב הצורפות אל העשייה האמנותית המודרנית. בין היתר חשף את התלמידים לזרמים עכשוויים כגון עיצוב דני, אקספרסיוניזם, אמנות קונספטואלית, מינימליסטית וזרמים אחרים. הוא שאף להביא לראיית הצורפות כאמנות עכשווית שאינה נחותה מסוגות אמנות אחרות. שנים לאחר מכן ציין גרשטיין כי מעורבותו בהוראה במחלקה לצורפות השפיעה עליו במעבר מן הציור אל הפיסול.
בשנים 1973 - 1974 השלים גרשטיין תואר שני במגמת גרפיקה אמנותית ב"סנט מרטין סקול אוף ארט" בלונדון. במסגרת לימודיו התנסה בתחריט ובדפוס משי. הוא שאף להביא לשילוב של תחריט ודפוס משי, אשר עד אז לא שולבו זה בזה. עם סיום הלימודים בלונדון זכה בפרס ראשון ובשני פרסי ציון לשבח בתחרות סוף השנה של סנט מרטין. בשנת 1974 חזר גרשטיין ל"בצלאל" והחל ליישם חלק מהרעיונות שהגה במהלך לימודי התואר השני. גרשטיין לקח את טכניקת דפוס המשי שהייתה נפוצה בעולם האמנות המודרנית באותה התקופה ויישם אותה בתחום השימוש באמייל. כבר אז ניתן היה להבחין בנטייתו לנסות לשלב מדיומים וטכנולוגיות מתקדמות בעולם האמנות, נטייה אשר תתבטא ביתר שאת בשימושו בלייזר בשנות ה-90. עד שנת 1985 שימש כמרצה בכיר ב"בצלאל".
אמן עצמאי.
תערוכתו הראשונה של גרשטיין בארץ הוצגה בגלריה "אנגל" בירושלים בשנת 1971, ועסקה ברישומים ובצבעי מים בעלי אופי פיגורטיבי. לאחר מכן הציג בשנת 1978 בבית האמנים בירושלים תערוכת ציורי שמן גדולים שעסקו בציורי פנים ושפת-ים, אשר זכתה לביקורות חמות. בין היתר הושווה גרשטיין לדייוויד הוקני, בשל העובדה ש"כהוקני, גם הוא בראש ובראשונה אמן-רישום עם חוש מעולה לצבע".
בשנים אלה הוביל גרשטיין מאבק למען מתן לגיטימציה לאמנות הפיגורטיבית אשר הייתה חריגה בנוף האמנות הישראלית הקונספטואלית בעיקרה. הוא נמנה באותן השנים על קומץ אמנים כגון אברהם אופק, איוון שוובל, אבישי אייל, אורי ליפשיץ ואחרים, אשר התמקדו באמנות פיגורטיבית-נרטיבית.
באותה תקופה החלה להתפתח מגמה הפוכה של ציור היפר-ריאליסטי בהשראת ישראל הירשברג, אשר אף בה לא מצא גרשטיין את מקומו. שאיפתו בשנים אלה הייתה ליצור ציור פיגורטיבי בעל סגנון אישי וחופשי - "אמנות בגובה העיניים". מאוחר יותר הסביר גרשטיין כי הדבר דומה ליצירת ספרות איכותית, אשר גדולתה ברבדיה השונים, כך שאדם יכול ליהנות הן מעיון והן מקריאה מעמיקה. גרשטיין שאף להעביר אמירות אודות העולם ואודות החיים, יחסים בין בני-אדם לבין עצמם ולסביבתם, ופחות אודות שפת האמנות עצמה. כך צייר גרשטיין זכרונות מעברו, כגון אמו רוכבת על אופניים, או ציור שלו ושל אחיו בגיל ילדות. בין השראותיו המרכזיות הייתה כתיבתו של חנוך לוין, שהציג באופן קומי-אירוני את הבלי העולם, וגרשטיין שאף להעביר דברים דומים בציור: "מה שחנוך לוין כתב, ניסיתי אני לבטא בציור: מערכות יחסים בין נשים לגברים, בתוך המשפחה... ציור גרוטסקי שכזה". השראה נוספת עבורו באותה תקופה היה הצייר ג'ורג' גרוס כלפיו חש קרבה, שכן עסק אף הוא במה שגרשטיין כינה "הקומדיה האנושית". בנוסף השפיעו עליו ציירים כגון דייוויד הוקני, פרננדו בוטרו' חוזה לואיס קואבס אשר נגעו בהוויה האנושית וביחסים בין בני-אדם.
שנות ה-70 והציור הפיגורטיבי.
בשנות ה-70 שילב גרשטיין בנסיונותיו אמירות אישיות עם דימויים פיגורטיביים, בעיקר בעבודות בצבעי מים וגואש על נייר. תחילה נועדו עבודות אלו להיות סקיצות עבור ציורי שמן גדולים על בד. אולם, עם הזמן מצא האמן עניין בעבודה בצבעי מים על נייר גרידא, והן הפכו למדיום העיקרי שלו. גרשטיין יצר סדרת ציורים אודות ילדותו שהתבססו על צילומים ישנים ועל זכרונות ילדות. סדרה נוספת עסקה בזיכרון חרות אצלו של אמו הרוכבת על אופניים ברחובות רמת-גן, מוטיב אשר לימים התפתח לסדרת רוכבי האופניים בשנות ה-90 ולאחריהן. מוטיב חוזר בעבודות בהן תיאר גרשטיין נופי-פנים של בתים היו החתול ואגרטלי פרחים, שביטאו עבור האמן "שלווה של שגרת היומיום". הן החתול והן אגרטלי הפרחים המשיכו ללוות את עבודותיו עשרות שנים לאחר מכן. תוך התעסקות במוטיבים אלה שאף גרשטיין "לברוח מהמציאות הישראלית הפוליטית לעבר שלווה אולימפית נטולת סערות". באמצע שנות ה-70 יצר סדרת ציורים של אנשים על שפת חוף ים, אשר הושפעו הן מזיכרונותיו של האמן מילדותו והן מהתבוננות. סדרת ציורים נוספת כללה את נופי שכונת עין כרם בה חי האמן באותה התקופה וששימשה כתפאורה לקומפוזיציות עתירות-דמויות שעסקו ביחסים בין אנשים ובין בני-זוג.
שנות ה-80 והניסיונות הראשונים בפיסול.
שאיפתו של גרשטיין לתאר את ההווי היומיומי בישראל באופן אירוני בשלה בשנות ה-80. בשנים אלה עסק גרשטיין בתיאור פיגורטיבי של פרקים מההוויה הישראלית, אשר נבעו בין היתר מזיכרונות ילדותו מתל אביב. הסדרה הראשונה תיארה מרפסות תל אביביות בסגנון באוהאוס באופי הומוריסטי-אירוני. סדרה זו נבעה מזיכרונות ילדותו של דור הוריו בתל אביב הקטנה והוא הביט עליהם בפליאה ובהומור. המתח בין דור הילדים הצברים לבין דור ההורים הגלותיים יחסית התבטא בציוריו. כך צייר בסדרה זו אנשים מבוגרים, בעלי אופי גלותי-משהו בפניהם, כפי שניבטו מעיני הילד הצבר הרואה את דור המדבר, דור מייסדי המדינה אשר עלו אליה בגיל צעיר, אך עדיין טבועה הייתה בהם מורשת הגלות. ניצניה של סדרה זו בעבודות של גרשטיין משנות ה-70, בעבודות צבעי מים וגואש על נייר, אשר חלקן עובדו לציורי שמן על בד. בשנות ה-80 פיתח גרשטיין סדרות אלו לכדי סדרה נוספת של ציורי אנשים הרוחצים בים-המלח. אודות סדרה זו כתב אברהם אילת: "שוכני המרפסות ירדו לים-המלח והם רובצים לחופו מרוחי-בוץ, חושפים את גופותיהם הוורדרדים לחסדי קרני השמש והמלח המטגנים אותם באיטיות".
במהלך שנים אלה, ועל אף ההדים החיוביים להם זכו ציוריו בעיתונות ובעולם האמנות, חש גרשטיין צורך בהתחדשות ובחיפוש כיוונים חדשים והרחבת גבולות הציור. במהלך השנים 1980-1987 עסק גרשטיין במקביל לציור גם בניסיונות פיסול בעץ, אשר היו "תלת-ממדיים אך שמרו על איכויותיהם הדו-ממדיות". גרשטיין שאף "להרחיב את גבולות הציור" לתחום תלת-ממדי. לאחר כמה ניסיונות של פיסול בחומר, אשר לא סיפקו את האמן, גילה את הרעיון של חיתוך האלמנטים והרכבתם יחד למעין פיסול בחלל. הרעיון לכך נבע בעת שירותו במילואים, כאשר פירק קופסת קרטון המשמשת מחסנית לתרמילים, צייר על מחיצותיה הפנימיים של הקופסה, ולאחר מכן הרכיב את הקופסה שנית. מכאן התגלגל הרעיון לציור על קרטון גדול-ממדים והרכבתו לפסלים תלת-ממדיים. לאחר מספר פסלים בקרטון המשיך גרשטיין לעץ ולאלומיניום דק. גרשטיין הגדיר שנים אלו כ"מאבק" בין הציור לפיסול, ודימה את יחסו לציור ליחסים אל רעיה, ומנגד את יחסו לפיסול למעין רומן מרתק ואסור.
בשנת 1981 הציג גרשטיין לראשונה עבודות פיסול אלו בגלריה הוראס ריכטר ביפו. צעד זה היה נועז עבור הצייר בן ה-36, אשר לא עסק או הציג פיסול קודם לכן. העבודות שהוצגו בתערוכה היו מאלומיניום ומעץ, חומרים אשר היוו המשך לנושאים בהם עסק בציור בשנות ה-70: אמו הרוכבת על אופניים, חתולים, אגרטלי פרחים ואלמנטים שונים של טבע דומם. בשנים שלאחר מכן הציג גרשטיין בשתי גלריות שהיו מרכזיות באותה התקופה, שרה גילת ורות דבל, שם הוצגו המשך ה"חיפושים" של האמן אחר השפה החדשה ששילבה ציור ותלת-מימד. בשנת 1984 נסע גרשטיין לניו יורק לראשונה מאז תום לימודיו שם, והחל לעבוד עם סוכנת האמנים מרילין גולדברג שהזמינה הפקה של שש סדרות מוגבלות של הדפסים על אלומיניום בשם "Art Cats". סדרה זו כללה נגזרות חתולים בהשראת 12 אמנים ידועים, החל מוואן גוך וכלה בפיקאסו וליכטנשטיין. בעקבות הפקת עבודות אלו הוזמן גרשטיין להציג תערוכה במוזיאון ישראל באגף הנוער. בתערוכה זו, אשר הוצגה בשנת 1987 בשם "מדודו לתלת-מימד", הוצגו פסלים "צבעוניים, עליזים, משעשעים ומזכירים צעצועים או מגזרות-נייר". תערוכה זו סיכמה את כל עבודתו של גרשטיין בפיסול תלת-ממדי בשבע השנים שחלפו עד אותו זמן, והיוותה עבור גרשטיין פריצת-דרך; רוב העבודות שהוצגו בתערוכה נרכשו על ידי אספני המוזיאון מחו"ל, ובעקבות זאת קיבל גרשטיין הזמנות לתערוכות רבות בארצות הברית ובקנדה. בשנים אלו המשיך להתמקד בפיסול והקדיש את רוב מרצו לפיתוח סגנונו הייחודי.
שנות ה-90, החזרה לציור וגילוי הלייזר.
בשנות ה-90 המשיך גרשטיין לפתח את פסליו, ובמקביל חזר לצייר בסגנון שהיווה המשך ישיר לסדרת המרפסות וים-המלח של שנות ה-70 וה-80. סדרת המכוניות שיצר באותה תקופה הציגה אנשים הנוסעים בתוך רכב, כאשר הצופה מתבונן למעשה בשמשה הקדמית של הרכב ו"מציץ" אל הנעשה בתוכו. בדומה למוטיב ההצצה אל תוך מרפסות תל אביב, גם כאן בחר גרשטיין להתמקד בעמדת המציץ החיצוני המביט בנהג דרך השמשה, אשר בו-זמנית משקפת את הסביבה. סדרה זו נוצרה בפריז במהלך שהותו של גרשטיין בקריית האמנים (cite des arts) בשנים 1990 - 1991.