בסוף 1960 שיחק בהצגה "הבוגד" מאת הנרי דנקר ב"תיאטרון האהל". הצגת הבכורה של המחזה נערכה ב־20 בנובמבר באותה שנה. לאחר מכן שר ב"להקת הצעירים" עם נחמה הנדל, שייקה לוי ויוסי פרוסט. ארבעה שירים של הלהקה ראו אור בתקליטון בשם "שירי נעמי שמר", שבו ניתן לאיינשטיין קרדיט בשם הבדוי "ארי גורן".
ביוני 1961 הופיע ב"מועדון החמאם" ביפו, בהצגות "משלי ערב" ו"תל אביב הקטנה". בספטמבר באותה שנה השתתף בצילומי הסרט "ניני" בתפקיד הדמות הגברית הראשית. אביו, יעקב איינשטיין, השתתף אף הוא בסרט כאביה של הדמות שגילם איינשטיין. הסרט לא זכה להצלחה רבה, ולימים סיפר איינשטיין שהוא מתחרט על שהשתתף בו.
במאי 1962 הקים איינשטיין צמד מוזיקלי עם הזמרת אילנה רובינא בשם "הגפרורים". השניים העלו מופע של שירי עם, אך לא הקליטו שירים באופן מקצועי. באותה שנה השתתף בהצגה "אירמה לה דוס", שבה גילם את אחד מהתפקידים הראשיים: הסרסור הקנאי. הופעת הבכורה בתיאטרון "הבימה" נערכה ב־10 בנובמבר 1962 מול אלפי חיילים וזכתה להצלחה רבה. ההשתתפות בהצגה זו זיכתה את איינשטיין בהערכה ציבורית ניכרת. בנובמבר 1963 שיחק איינשטיין בסרטו של אפרים קישון "סאלח שבתי", שעלה ב־1964, בו גילם את דמותו של זיגי, בן קיבוץ המתאהב בבתו של סאלח (גאולה נוני). איינשטיין הקליט עבור הסרט בדואט עם נוני את השיר "לי ולך". בדצמבר באותה שנה החל לשחק בהצגה "בילי בדאי".
במקביל חבר בסוף 1963 לזמרים יהורם גאון ובני אמדורסקי להקמת להקה חדשה, "שלישיית גשר הירקון". עוד לפני שהחלה הלהקה להופיע השתתפו חבריה בפברואר 1964 בצילומי הסרט "דליה והמלחים". באפריל 1964 עלתה תוכניתה הראשונה של הלהקה, "אהבה ראשונה". המופע לא זכה להצלחה רבה בתחילת דרכו, אך תוך זמן קצר קצר תשואות רבות. אלבומה הראשון של הלהקה, "אהבה ראשונה", יצא בתחילת 1965. רבים משיריו הפכו להיטים, ובהם "אל תעברי לבד", "לילה בחוף אכזיב", "איילת אהבים", "אם רק תבואי בחמש", "אהבת פועלי הבניין", "כשאור דולק בחלונך", "סרנדה לך" ו"איזה יום יפה".
איינשטיין השתתף בפסטיבל הזמר והפזמון 1964, שבו שר לבדו את השיר "הרחק בלילה", ועם "שלישיית גשר הירקון" את השיר "אותך". בפסטיבל הזמר והפזמון 1965 שב לתחרות, וזכה במקום הראשון עם השיר "איילת החן", שאותו ביצעה גם יפה ירקוני בביצוע נפרד, למילים של עודד בצר, ללחן של נתן שחר ולעיבוד של יצחק גרציאני. לאחר התוכנית הראשונה של "שלישיית גשר הירקון" עזב גאון את הלהקה והוחלף בישראל גוריון. השלישייה המחודשת העלתה תוכנית בשם "התוכנית החדשה", והתקליט שליווה אותה יצא ב־1966 ונמכר היטב. בין שיריו המוכרים היו "סימן שאתה צעיר", "כחולה כחלום" ו"הכל בגלל האהבה".
אלבומי סולו ראשונים ו"החלונות הגבוהים".
אלבום הסולו המלא הראשון של איינשטיין, "שר בשבילך", יצא במרץ 1966. כמעט את כל שירי האלבום כתבה המוזיקאית דפנה אילת, ששיחקה קודם לכן לצידו של איינשטיין בהצגה "בילי בדאי". חלק מהשירים שכתבה הלחינה בעצמה, וחלק היו תרגומים לשירים לועזיים. שיר אחד כתבה המשוררת תרצה אתר. על העיבודים הופקד סטו הכהן. בין השירים הבולטים באלבום היו "הלילה הזה", "אל תבכי ילדה" ו"הגשם מתופף". באותה שנה הקליט איינשטיין שיר נוסף שלא נכלל באלבום, "בתי עינת", שכתבה הפזמונאית לאה לופנפלד ללחן של משה וילנסקי.
בפסטיבל הזמר והפזמון 1966 זכה איינשטיין שוב, הפעם עם השיר "ליל סתיו", למילים של חיה כהן, ללחן של חיים צור ולעיבוד של שמעון כהן. בפסטיבל זה שר איינשטיין עם שלישיית גשר הירקון את השיר "ריח תפוח אודם שני", שהגיע למקום השני בתחרות, וכן שר לבדו את השיר "לא פעם, בקיץ" ועם השלישייה את "בואי ילדה". את השיר "ליל סתיו" שרה בפסטיבל גם יפה ירקוני, ולאחר הפסטיבל הוציאו השניים תקליטון משותף ובו ארבעה שירים: "ליל סתיו", "קרה זה רק הפעם", "לו הייתי" וגרסתם לשירם של הביטלס "Yesterday", שבתרגומו העברי של חיים חפר נקרא "רק אתמול".
באותה שנה הקים את להקת הליווי הראשונה שלו, "האיינשטיינים", שכללה את דוד קריבושי באורגן ועיבודים, אלי מזרחי בתופים, שמוליק ארוך בבס וריצ'רד פרץ בגיטרה חשמלית. יחד איתם הקליט איינשטיין תקליטון של גרסאות כיסוי. נכללו בו גרסה עברית לשיר "Do You Want to Know a Secret" של הביטלס שבמילותיו העבריות של יורם טהרלב נקרא "מזל", גרסה עברית של לאה נאור ל-"The House of the Rising Sun" בשם "רחוק רחוק מכאן", גרסה מחודשת לשירם של הדודאים "ערב של שושנים" וגרסה עברית לשיר "עץ הלימון". במקביל חברו איינשטיין ולהקת הליווי לשחקן שייקה אופיר להעלאת מחזה מוזיקלי בשם "ערב של שושנים", שכלל שירים של איינשטיין לצד קטעי משחק של אופיר. המופע לא האריך ימים, והסתיים באוקטובר 1966 עם נסיעתו של אופיר לפריז.
לאחת ההופעות של המופע "ערב של שושנים" הגיעו שמוליק קראוס וג'וזי כץ, ולאחר ההופעה נפגשו עם איינשטיין והשמיעו לו שירים אחדים ששרו בהופעותיהם המשותפות. איינשטיין אהב את השירים, והשלושה החליטו על הקמת להקה חדשה, "החלונות הגבוהים". השלושה החלו מייד לאחר מכן בחזרות ובעבודה על שירים חדשים, כולם על פי לחנים של קראוס. אנשים אחדים שהיו מקורבים לאיינשטיין טענו שהצטרפות ללהקה חדשה לאחר שכבר הוציא אלבום סולו תהיה נסיגה לאחור מבחינתו, אך הוא החליט להתעלם מדעות אלו ולהתמקד בפעילותה של הלהקה. בפברואר 1967 החלה הלהקה בסיבוב הופעות, והופעותיה זכו לשבחים רבים בכלי התקשורת. באפריל באותה שנה יצא אלבומה היחיד של הלהקה. איינשטיין כתב שניים משירי האלבום: "כל השבוע לך" ו"אז מה". שירים רבים אחרים מהאלבום הפכו ללהיטים, ובהם "זמר נוגה" ("התשמע קולי..."), "יחזקאל" ו"אינך יכולה".
לאחר יציאת האלבום המשיכה להקת "החלונות הגבוהים" בהופעות רבות, וביולי 1967 הצטרפה ללהקת המחול של יונתן כרמון למופע ברחבי העולם. הלהקה הופיעה תחילה בבלגיה ולאחר מכן באולימפיה שבפריז ובאולם הסיסטינה ברומא, והופעותיה זכו לאהדה רבה. בספטמבר באותה שנה חש איינשטיין געגועים לישראל, והחליט לעזוב את המופע ולשוב לארץ. מייד עם שובו החל בעבודה על שירים חדשים עם שלום חנוך, שאותו פגש לראשונה כמה חודשים קודם לכן. המפגש הראשון ביניהם חל במועדון בשם "החלונות הגבוהים", ששמוליק קראוס היה אחד מבעליו, ובו הרבתה הלהקה להופיע. לאחר אחת מהופעות הלהקה פגש חנוך את חבריה, והציג להם את יכולות נגינתו בגיטרה. איינשטיין התרשם עמוקות מחנוך ובסוף אותה שנה הוציא תקליטון ובו ארבעה מלחניו של חנוך: "הגר" (מילים: חנוך), "ריסים" (מילים: מאיר אריאל), "שבת המלכה" (מילים: איינשטיין) ו"פתאום בלעדיו" (מילים: מאיר אריאל). תקליטון נוסף שהוציא באותה שנה נקרא "אני מרגיש כמו מלך", ובו גרסה עברית לשיר "Mellow Yellow" בשם "אני מרגיש כמו מלך" ושלושה שירים בגרסאות מחודשות: "לא פעם בקיץ", "הכאב הזה" ו"ירושלים של זהב".
באותה תקופה השיג קראוס חוזה בלונדון עם חברת התקליטים CBS, ולבקשתו שב איינשטיין להופיע עם "החלונות הגבוהים". הלהקה הקליטה בלונדון שני שירים באנגלית: "Maybe Someday" ו־"Your Eyes", שאת שניהם כתב ראלף מרפי. שניהם הוקלטו גם בעברית, במילים שחיבר איינשטיין, והם ראו אור על גבי תקליטון שיצא בישראל בפברואר 1968 בשמות "כמה נעים" ו"בואו ונרים כוסית". לאורך 1968 הופיעה הלהקה כמה פעמים בתוכניות טלוויזיה שונות באנגליה, עד שאיינשטיין חש בשנית געגועים לישראל, והחליט לעזוב את הלהקה סופית.
לאחר שעזב את החלונות הגבוהים ושב לישראל המשיך איינשטיין בעבודתו עם שלום חנוך, הפעם על אלבום שלם. ביולי 1968 התפרסם השיר הראשון מאלבום זה, "הימים הארוכים העצובים", שכתב איינשטיין בזמן שהייתו בלונדון מתוך געגועים לבתו. בספטמבר התפרסם השיר "מכופף הבננות", שהלחין חנוך על פי מילים של מאיר אריאל, ובאוקטובר יצא לאור האלבום השלם, "מזל גדי". היה זה אלבומו הראשון של איינשטיין בחברת סי.בי.אס. את כל שירי האלבום, רבים מהם שירי ילדים, הלחין חנוך. הם עוטרו בעיבוד תזמורתי עשיר של אלכס וייס ותזמורת סי.בי.אס. על אף שחנוך הביע לא אחת מורת רוח מהעידון שכפו עיבודיו של וייס על הלחנים שלו, שכבר נטו בבירור לרוק, הציבור היה מרוצה מהאלבום, והביקורות שהוא קיבל היו חיוביות ברובן. "מזל גדי" קידם משמעותית את הקריירה של איינשטיין, וכולל כמה מהמוכרים שבלהיטיו, בהם "רוח רוח" (מילים: מרים ילן-שטקליס), "האדון הרופא" (מילים: חנוך), "מה שהיה היה" (מילים: חנוך) ו"כהה כהה" (מילים: חנוך).
בספטמבר 1968 יצא איינשטיין לסיבוב הופעות שליווה את האלבום "מזל גדי" עם להקת ליווי חדשה: "הברנשים של פיאמנטה". היא כללה את אלברט פיאמנטה בסקסופון, אהרלה קמינסקי בתופים, שמוליק ארוך בגיטרה בס, יעקב נגר בקלידים, עוזי מלמד בחצוצרה וזאב דיקוורט בסקסופון. בהופעות אלו הציג איינשטיין שני שירים חדשים: "בית הערבה" (חיים חפר ועמוס קינן / שמוליק קראוס) וגרסה עברית לשירם של הביטלס "Ob-La-Di, Ob-La-Da". השיר "בית הערבה" נועד במקור לשלישיית "החלונות הגבוהים", אך עם התפרקותה וגניזת אלבומה השני הוא הועבר לאיינשטיין.
עם מעברו של איינשטיין מ"הד ארצי" ל"סי.בי.אס" הוציאה חברת "הד ארצי" באוקטובר באותה שנה אלבום אוסף בשם "ישן וגם חדש", שריכז חלק מהקלטותיו בחברה במהלך שנות ה-60. נכללו בו כל שירי התקליטון "הגר" לצד הקלטות מוקדמות יותר כמו "עיר לבנה", "השעות הקטנות של הלילה" ו"אני מרגיש כמו מלך", שהופיעו בתקליטונים השונים שהקליט איינשטיין בהד ארצי, וכן שירים מתקופת שלישיית גשר הירקון והחלונות הגבוהים.