חכם שלמה טולידאנו נולד לאימו מרת מרים ולאביו חכם אברהם בשנת תרס"ד (1904) במכנאס שבמרוקו.
ראשית תורתו בעירו מכנאס, שם למד תורה בישיבת החכם יצחק סבאג במחיצת חברו הטוב חכם שלום משאש, איתו למד בחברותא כחמש תמימות, במהלכן כתב חכם שלום משאש את ספרו 'מזרח שמ"ש', שהודפס בשנת תרצ"ג (1933).
חכם שלמה טולידאנו נשא לאשה את מרת רבקה, ביתו של רב העיר מכנאס, חכם רפאל ברוך טולידאנו. מרת רבקה, הקדישה מזמנה ללימוד התורה, וקנתה בקיאות בהלכה ובאגדה. יחדיו פתחו ביתם לחולים וגלמודים שלא היה מי שיטפל בהם, והיו דואגים לכל מחסורם הנפשי והפיזי. לימים נולדו להם שני בנים ושתי בנות. שני הבנים חכם גבריאל וחכם מיכאל, הקימו את ישיבת 'אור ברוך' בירושלים, הנקראת על שם סבם.
חכם שלמה טולידאנו היה מגיד מישרים בעירו, ואל דרשותיו נמשכו המונים. ייחודו היה בכך ששינה את סגנון הדרשות המסורתי, לסגנון מותאם לאותו הזמן, שהושפע מרוח תרבותה של צרפת.
חכם שלמה טולידאנו עבד לפרנסתו, והיה נהנה מיגיע כפיו. בתחילה השכיר את עצמו להיות עוזרו של רופא העיר, והיה מלווהו ונושא את כליו לבתיהם של החולים היהודים. במשך הזמן התבונן ולמד ממעשיו של הרופא עד שנהייה רופא בעצמו והיה מסתובב בבתים, עוזר מרפא ומייעץ ומעודד לכל מי שנתבקש חינם אין כסף, ביום ובלילה, ללא שעות קבלת קהל כלל, עד שנקרא בפי כל 'רבי שלמה הרופא'.
בשנת תשכ"ו (1967) חכם שלמה טולידאנו זכה ועלה לארץ ישראל והתיישב בעיר בני ברק. חכם שלמה טולידאנו פתח, יחד עם שותפו יצחק אוחנה, חנות לאביזרי נעליים. אך בהיותו כבן 65 עזב את עבודתו, והקדיש את שארית ימיו ללימוד תורה ולגמילות חסדים.
חכם שלמה טולידאנו זכה לאריכות ימים ושנים, ונפטר בשיבה טובה ביום י"א תשרי בשנת תשנ"ז (1997).
חכם שלמה טולידאנו חיבר ספר הלכתי על שולחן ערוך חלק 'יורה דעה', פרי לימודו בנעוריו עם חכם שלום משאש, ספר זה נותר בכתב יד. כן חיבר ספר דרשות 'יקהל שלמה' ב' חלקים, בו קיבץ וערך את דרשותיו לפי סדר פרשיות השבוע, ספר זה נדפס ע"י מכון 'בני יששכר' בשנת תשס"ד (2004).