טולדנו עלה לארץ לאחר שזייף את חתימת אביו על הטופס שאישר את עלייתו ארצה.
תחילה שהתה הקבוצה מספר חודשים במחנה עולים של הסוכנות היהודית במרסיי שבצרפת, ומשם עלו לארץ ונקלטו בקיבוץ רוחמה.
כבר כנער גילה טולדנו את כישרונו במוזיקה, והחל להתפרסם בארץ בתוכנית הרדיו "תשואות ראשונות". לתוכנית זו שלח שירים שכתב והלחין בעצמו. המלחין משה וילנסקי, ששמע את שיריו בתוכנית, הזמין אותו לשיר את השיר "זוהי יפו", שהלחין למילים של יוסי גמזו עבור סרט תיעודי קצר על העיר יפו. השיר זכה להצלחה רבה, והביא לפרסומו הראשון של טולדנו עוד בטרם גיוסו לצבא.
את שירותו הצבאי העביר בלהקת גייסות השריון, שבה היה שותף לתוכניות "שישה ימים בטנק" ו"פשוט שריונר". שם הוא שירת לצד תיקי דיין, דליה כהן, שאחר כך הפכה לזמרת בזכות עצמה. כסולן התבלט בשירים "אחי הצעיר יהודה", "שלא לאהוב אותך איך אפשר", "מי שחלם" ו"שריונים 69".
תחילת קריירת הסולו.
עוד במהלך שירותו הצבאי בשנת 1968, הוציא את אלבום הסולו הראשון שלו, "אבי טולדנו עם דוד קריבושי ותזמורתו", בעיבודיו של דוד קריבושי. נכללו בו השירים "זוהי יפו" ו"שלא לאהוב אותך איך אפשר".
בשנת 1969 השתתף בפסטיבל הזמר עם השירים "את הרוח" (רימונה דינור/רפי בן-משה) ו"בדרך חזרה" (אהוד מנור/נורית הירש), שאיתו זכה במקום השלישי.
באותה שנה יצא אלבומו השני "אבי", ובו להיטים נוספים שיצרו מנור והירש, כ"איך עף הזמן" ו"ראיתי את הקיץ". שיר נוסף מוכר מהאלבום היה גרסת כיסוי בעברית לשירה של מרי הופקין "כאלה היו הימים", בתרגומו של מיקי הרטבי (הגרסה המקורית בעברית הוקלטה לראשונה על ידי שולי נתן). הרטבי תרגם עבור האלבום גם את שירו של טום ג'ונס "Delilah", שבגרסתו העברית נקרא "עם בוא הלילה". את שם האלבום ליוותה כתבה המרמזת על פרסומו של טולדנו, עם בדיחה סמלית: "כאשר בתך אומרת 'אבי', היא אינה מתכוונת לבעלך, אלא לאבי טולדנו...". כמו כן הקליט טולדנו באותה שנה את השיר "עם רדת יום" (יעקב שבתאי/יוחנן זראי) בעבור הסרט "מצור". הצלחותיו באותה שנה הביאו לזכייתו בתואר זמר השנה במצעד הפזמונים העברי השנתי של קול ישראל.
בשנת 1970 יצא אלבומו השלישי "בגן ערפילי", שמתוכו התפרסמו השירים "בעיר זרה" (אהוד מנור/יוחנן זראי) ו"שושנת הרוחות", שטולדנו הלחין למילים של דידי מנוסי.
באותה שנה זכה במקום הראשון בפסטיבל לשירי ילדים שנערך בפעם הראשונה, עם השיר "למה ככה", שדודו ברק כתב ושייקה פייקוב הלחין. שותפתו לזכייה זו הייתה עירית ענבי, שהייתה אז ילדה בת עשר. השיר בביצוע השניים זכה לפופולריות רבה, והוא אחד השירים המזוהים ביותר עם הפסטיבל. שיר זה הביא גם לפרסומה של ענבי. שיר זה שובץ לפסקול הסרט "אריאנה" (1971) בו שר טולדנו גם את שיר הנושא לסרט. טולדנו המשיך להשתתף גם בפסטיבלים הבאים עם השירים "חיפושית הקצב", "חג יובל" ו"שיר בלה לה לה".
באותה שנה טולדנו הוציא את אלבומו הרביעי הנקרא "בשירי עמים", ובו שירי עם ממדינות שונות בתרגום לעברית. אחד המוכרים שבהם הוא "אבירים של שולחן עגול", שכתבה מרים ילן שטקליס על פי לחן עממי צרפתי.
המשך שנות השבעים.
בשנת 1971 השתתף בסרטו של ג'ורג' עובדיה "אריאנה", וביצע בו את שיר הנושא. בשנת 1972 השתתף בשנית בפסטיבל שירי הילדים עם השיר "חג יובל", שנוצר גם הוא על ידי דודו ברק ושייקה פייקוב.
בשנת 1974 יצא אלבומו החמישי "סתם בן אדם", שהורכב ברובו משירים שהלחין למילים של אבי קורן. הלהיט הגדול באלבום היה "מה חשוב היום", שהלחין טולדנו עם אריה גור למילים של עוזי חיטמן. מהשירים שכתב קורן התפרסם "אני זוכר רק שיר".
בשנה זו זכה טולדנו בפסטיבל שירי משוררים לילדים עם השיר "ידידי טינטן", שקובי אשרת הלחין למילים של מרים ילן שטקליס. שיר זה הפך ללהיט ענק עד היום. (בפזמון השיר "לאב בוי" של הזמרת דנה אינטרנשיונל צוטטו שתי השורות הראשונות של פזמון השיר הנ"ל: "והוא ישן במיטתי/ והוא אוכל מצלחתי").
בשנת 1976 הוציא את האלבום "זירת חיי", ובו השיר "בתחנה המרכזית", שעמו זכה שנה קודם לכן ב"פסטיבל שירי הבירה". את השיר רוני וייס הלחין למילים של משה בן שאול, ופרט לו, טולדנו הלחין את כל שירי האלבום.
לקראת סוף שנות השבעים יצא למסע הופעות באירופה.
בשנת 1978 יצא עם מופע יחיד בשם "לה בוהם" - ערב שנסונים של שארל אזנבור, שבעצמו הגיע ונכח בהופעת הבכורה. המילים העבריות לשירים נכתבו בידי פזמונאים שונים, ובהם אהוד מנור ודודו טופז. מרבית השירים הוקלטו בהמשך באוסף "השנסונייר". הגרסה העברית לשיר "שתי גיטרות" (בתרגומו של טופז) זכתה בתחילת שנות השמונים לגרסת כיסוי על ידי דורון מזר.
בשנת 1979 הלחין את השיר "שולם ברוגז", שאיתו זכה מייק בורשטיין במקום הראשון בפסטיבל לשירי ילדים מספר 10.
שנות השמונים.
לאחר מספר שנים בצרפת שב טולדנו לישראל.
בשנת 1980 הוציא את האלבום "צלע", שאת רוב שיריו כתבה שמרית אור. מתוכו זכו להצלחה הלהיטים "ליאורה", שנכתב לאשתו, ליאורה טולדנו, "אדם נשאר ילד" ו"כל חיי", שסיים במקום הלשישי במצעד הפזמונים העברי השנתי של גלי צה"ל לשנת תש"ם.
במרץ 1981 השתתף לראשונה בתחרות הקדם-אירוויזיון עם השיר "קרנבל", שהלחין למילים של שמרית אור, ועיבוד של ננסי ברנדס. השיר זכה להצלחה והגיע למקום השלישי בתחרות.
ב-1982 השתתף בשנית בקדם אירוויזיון עם השיר "הורה", שהלחין למילים של יורם טהרלב, ועימו זכה במקום הראשון. בעקבות זאת ייצג טולדנו את ישראל באירוויזיון 1982, והגיע עם השיר למקום השני בתחרות. "הורה" ו"קרנבל" והשיר "ההצגה נמשכת" נכללו באלבומו של טולדנו "מפגשים", שיצא באותה שנה. כהמשך לאלבומו הקודם, גם באלבום זה נכתבו רוב השירים בידי הפזמונאית שמרית אור. בנוסף עפרה חזה הקליטה באותה שנה את לחנו של טולדנו לשיר "מכתב אהבה", שהופיע באלבומה "פיתויים". בשנה זו הוא זכה בתואר זמר השנה במצעד הפזמונים השנתי של גלי צה"ל, והקליט בדואט עם "זמרת השנה", עפרה חזה, את "שיר הנבחרים" של התחנה - "אחרי החגים". טולדנו הלחין את השיר למילים של אהוד מנור. בדצמבר אותה שנה השתתף בשירוויזון מספר 4 עם השיר "אבא אבא", שהלחין למילים של יורם טהרלב, ועיבוד של ננסי ברנדס. השיר זכה להצלחה רבה, והגיע למקום הראשון בתחרות.
בשנת 1983 הלחין לעופרה חזה את השיר "חי", שזכה גם הוא בקדם אירוויזיון' ובמקום השני באירוויזיון עצמו. השיר נבחר כ"שיר השנה" במצעד הפזמונים השנתי של רשת ג' לשנת תשמ"ג. בדצמבר אותה שנה, זכה במקום הראשון בפסטיבל שירי הילדים מספר 14 עם השיר "ביחד", שהלחין למילים של ענת שרתוק-שרים, ועיבוד של אלדד שרים.
בשנת 1984 יצא במופע יחיד שגם תועד לאלבום, "תעודת זהות", בבית ליסין, המבוסס על חייו. את רוב שירי המופע, יורם טהרלב כתב. ביניהם: "קוראים לי אבי טולדנו", אשר היה מעין "היכרות" קומית איתו.
עוד באותה שנה יצא אלבומו "אני רק עובר", שבו נכלל הדואט עם חזה "אחרי החגים". מהאלבום הצליח שיר הנושא (מילים: ענת שרים, עיבוד: אלדד שרים), שדורג במקום ה-27 במצעד הפזמונים השנתי של רשת ג' לשנת תשמ"ד. בדצמבר אותה שנה התארח בפסטיבל שירי הילדים מספר 15 עם השיר "למה במכות", שהלחין למילים של אהוד מנור, ועיבוד של אורי קריב.
בקדם אירוויזיון בשנת 1985 התחרתה ירדנה ארזי עם שיר שהלחין לה טולדנו, "עוד נגיע", למילים של אהוד מנור ועיבוד של אלדד שרים. השיר זכה להצלחה והגיע למקום ה-3 בתחרות.
ב-1986 הלחין טולדנו לקדם האירוויזיון, בעבור חיים משה, את שירה של לאה לופנפלד "לחיים" (עיבוד: ננסי ברנדס). השיר זכה להצלחה, והגיע אף הוא למקום ה-3 בתחרות.
עוד ב-1986 יצא אלבומו של טולדנו "תרקדי את הלילה". שיר הנושא, שטולדנו כתב והלחין, לעיבוד דאנס של יזהר אשדות, זכה להצלחה רבה, ודורג במקום ה-10 במצעד הפזמונים השנתי תשמ"ו של רשת ג'. גם השיר "בכל הכוח" מהאלבום, שאת מילותיו כתב שמוליק קלוסקי, ועיבד ננסי ברנדס זכה להצלחה, ודורג במקום ה-17 במצעד השנתי.
בשנת 1987 השתתף במחזמר "עלובי החיים" בתיאטרון הקאמרי והוציא את תקליט השדרים "אל תעשו חשבון עליי", שעיבד קובי אושרת.
בסוף שנת 1988 הוציא את האלבום "ויקטור", שבו כתב לראשונה את מרבית מילות השירים, מלבד "הבמה לוהטת" ו"מאהבה אני נשבר" אותם כתב שמוליק קלוסקי. אלדד שרים עיבד את שירי האלבום.
במרץ 1989 ניסה את כוחו שוב בתחרות הקדם אירוויזיון עם השיר "דיינו" שהלחין, למילים של אהוד מנור, ועיבוד של ננסי ברנדס. השיר הגיע למקום השני בתחרות, 8 נקודות מתחת לשיר הזוכה "דרך המלך" של הצמד גילי וגלית.
שנות התשעים.
ב-1990 הוציא את האלבום "שר חנוך לוין", המורכב כולו מלחניו לשירים של חנוך לוין. אחדים מהם, כ"שחמט" ו"התעמלות בוקר", התפרסמו קודם לכן בלחנים אחרים. אילן וירצברג עיבד את כל שירי האלבום. עוד בשנת 1990 צילם סרט תיעודי במרוקו על סיפור חייו שנקרא "בית לבן". הסרט שודר בערוץ הראשון.
לקדם אירוויזיון 1991 הלחין את "הבה נגילה גילה", שביצע בתחרות אורי פיינמן.
בשנת 1992 הוציא את האלבום "מרוקר", שהכיל ברובו גרסאות עבריות למנגינות מרוקאיות עממיות. את הטקסטים כתבו דודו ברק ואהוד מנור. ננסי ברנדס ודודי רוזנטל עיבדו את שירי האלבום, מלבד השיר "בית לבן", אותו עיבד אילן וירצברג וכתב טולדנו בעצמו.
בשנת 1993 יצא אלבום אוסף של טולדנו בשם "קול שירי". באלבום נכללה גרסה חדשה של טולדנו לשיר "זוהי יפו". אגב, זהו האוסף הראשון שלו שיצא על גבי פורמט CD.
באותה שנה השתתף בסרט "הירושה" של הבמאי אמנון רובינשטיין לצידם של אלון אבוטבול ויעל אבקסיס. טולדנו גם שר את שיר הנושא של הסרט, "אלך איתך", בדואט עם בתו טל.