כבר בהיותו בן 15 שנים שיחק במשחקי אימון בקבוצה הבוגרת, שבה השתלב ב-16 ביולי 1949 במשחק נגד הפועל רמת-גן בו ניצחו הצהובים 2:3. גולדשטיין השתלב כמחליף במחצית השנייה כקיצוני שמאלי. עם הזמן השתלב בהרכב הראשון החל מ-1950 בעת מסעה של הקבוצה לתורכיה, בתפקידו כמקשר ימני וכחלק מהחמישיה המובילה, שבשלב מסויים היוותה גם את החמישיה המובילה של נבחרת ישאל. עם מסע מכבי ישראל לאנגליה ב-1954, נשאר יחד עם יוסל'ה מירמוביץ, ושניהם שיחקו בקבוצת החובבים "וינגייט". השניים אף נבחרו לשחק בנבחרת החובבים של לונדון.
בשנים 1957-1955 שיחק בקבוצת ה"ריינג'רס" הדרום-אפריקנית והפך לשחקן החצי מקצועני הראשון בארץ. עם חזרתו לארץ השתלב שוב בקבוצה ובנבחרת ישראל. בעת ששיחק בדרום-אפריקה צורף למסעה של מכבי תל-אביב לארצות-הברית וקנדה.
על אף שהותו מחוץ לגבולות המדינה, מעולם לא עזב את מכבי, ומעולם לא נכנס להסגר. הוא שיחק בקבוצה עד סוף עונת 1962-1961. לאורך השנים ובעקבות יכולותיו נחשב גולדשטיין למנוע של מכבי והספיק לזכות בארבע אליפויות ( 1949/1950, 1951/1952, 1953/1954, 1957/1958) ושלושה גביעי מדינה (1953/1954, 1957/1958, 1958/1959). בנוסף רשם 25 הופעות במדי נבחרת ישראל בהן כבש שער אחד.
גולדשטיין אף אימן כדורגל בקבוצות שונות ואת דרכוזו סיים במכבי תל-אביב בשנים 1990-1987, כאשר אימן בקבוצת ילדים מכבי "משה", ושתי קבוצות נערים.