חכם שלמה מלכה נולד לאמו ולאביו ביום ט"ו באב בשנת תרל"ח (1878) באספלו שבתפילאלאת שבמרוקו.
בשנת תרנ"ו (1896) נשא לאשה את חנה לבית אסולין, ילידת טנג'יר.
בשנת תרנ"ח (1898) חכם שלמה מלכה ורעייתו עלו לארץ ישראל. בה הוא המשיך את לימודיו בישיבות בטבריה ובצפת, והוסמך לרבנות. לאחר זמן שב למרוקו, חזר ועלה לארץ ישראל, ושימש חבר בבית הדין הרבני בטבריה, מקום מושבו.
בשנת תרס"ח (1908) חכם שלמה מלכה נענה לבקשתו של חכם באשי אליהו בכור חזן, רבה של מצרים, לשרת בקודש בעיר אומדורמאן, שבסודן. לאחר תקופה הביא לסודן גם את רעייתו חנה, ואת שתי בנותיו אסתר ופורטונה. באומדורמאן נולדו להם עוד ארבע בנות וארבעה בנים.
העיר אומדורמאן, הגדולה שבערי סודאן, החלה להתאושש משנות הג'יהאד הקשות, שהכריז המהדי מוחמד אחמד, בשנת תרמ"א (1881). המהדי שהצליח לסלק את השלטון התורכי-המצרי מסודן, הקים מדינה אסלאמית גיהאדיסטית, שהובסה ע"י כוחות בריטיים רק בשנת תרנ"ט (1899).
חכם שלמה מלכה החל לקומם את החיים הרוחניים בעיר אומדורמאן. הוא שימש יחידי בקודש, והיה גם מוהל, שוחט וחזן. חכם שלמה מלכה קבע בית קבע לשמש בית כנסת, ודאג להביא ספרי תורה ממצרים ומישראל.
אחד הדברים הראשונים שחכם שלמה מלכה התמודד איתם, היה גיורן של הנשים היהודיות, שאולצו להתאסלם בשנות הג'יהאד של המהדי. הוא הזמין לעירו את גדולי חכמי מצרים החכם באשי אליהו בכור חזן ואת חכם אברהם אבוכזיר, ששימשו כבית דין לגיור.
חכם שלמה מלכה נודע כאיש רוח ומעשה גם בקרב המוסלמים והנוצרים. הוא לא התפרנס מהקהילה, והיה לבעלים של טחנה להפקת שמן שומשום, מפעל לייצור מרצפות ובית חרושת לאטריות.
חכם שלמה מלכה הקפיד לשמור על קשריו עם הקהילה היהודית במצרים. הוא פרסם מאמרים רבים בשבועון אל-שמס - שבועון הקהילה היהודית, שיצא לאור בערבית בין השנים תרצ"ד-תש"ח (1934-1948). מדי שנה, היה חכם שלמה מלכה מבקר את בתו פורטונה במצרים, היה נושא דרשות בציבור ונפגש עם ראשי הקהל.
בשנת תש"ב (1942), בזמן מלחמת העולם השנייה, חכם שלמה מלכה נסע לירושלים, ונועד עם הרבנים הראשיים הראשון לציון חכם בן ציון מאיר חי עוזיאל והרב הראשי הרב יצחק אייזיק הלוי הרצוג.
חכם שלמה מלכה נפטר ביום ה' בניסן תש"ט (1949) בחרטום. בית הכנסת בחרטום הוקדש לזכרו ונקרא 'אוהל שלמה'. לוח זהה נקבע בקומה השנייה בבית הכנסת יש"א ברכה בירושלים.
בשנת תשל"ז (1977) הובא ארונו של חכם שלמה מלכה לירושלים ונטמן בחלקת יהודי סודאן בגבעת שאול.
חכם שלמה מלכה פרסם מאמריו באל-שמס. מאמריו, העוסקים בפרשיות השבוע, יצאו לאור גם כספר.