הפיוט "שלום עליכם" (ראו בלחן גולדפרב ושם עוד פרטים והפניות) בלחן הבית של השיר הספרדי-יהודי "המלך נמרוד".

המילים "מלאכי רחמים" נוספו בלחן זה בלבד. הנוסח "מלאכי השלום" במקום "מלאכי השרת" קיים במקורות נוספים. 

נוסח המילים המובא כאן תואם את הקלטת להקת המרוקאים. הבית "בואכם בשלום" מושר בו אחרי "ברכוני לשלום" והבית "צאתכם לשלום" חסר בו.

רבקה הבסי מרחיבה על השיר "המלך נמרוד", בין היתר על סמך מחקרו של אדוין סרוסי (ראה אור בפרק השישי של ספרו Sonic Ruins of Modernity: Judeo-Spanish Folksongs Today):

 הלחן שלפיו מושר הפיוט "שלום עליכם" הוא לחן הבית של אחד השירים בלדינו המוכרים ביותר בישראל היום. השיר מוכר בשם "המלך נמרוד" (מתוך שורת הפתיחה שלו), או בשם "אברהם אבינו", על פי פתיחת הפזמון החוזר. הנוסח המוכר של שיר לדינו זה הוא נוסח מקוצר במיוחד של שיר בסוגת הקופלה בלדינו (בן 35 בתים לפחות), שנכתב במאה ה-י"ח באחת מקהילות היהודים הספרדים באימפריה העות'מנית. השיר מספר את קורות חייו של אברהם אבינו והכרתו באל היחיד בורא העולם, בהסתמך על מדרשים ומקורות יהודיים שקדמו לו. בספרות המחקרית של השירה בלדינו השיר מוכר בכותרת "לידתו וייעודו של אברהם".

עדות לכך שהשיר זומר יש כבר משנת 1836, במהדורה מבלגרד של הספר "זמירות ישראל" מפיוטי ישראל נג'ארה כתוב לשיר את אחד הפיוטים בלחן "המלך נמרוד". ואולם, ודאי מדובר בלחן אחר. 
הלחן הנוכחי נושא צביון פופולרי ספרדי (לאו דווקא יהודי) והוא עלה בהקלטות שדה רק מקהילות היהודים דוברי הספרדית (בדיאלקט הקרוי חכיתיה) בצפון מרוקו. נוסף בו הפזמון החוזר (שאינו מבוצע ב"שלום עליכם"). העדות המוקדמת ביותר ללחן הזה היא בעיבוד לקול ופסנתר מאת וולף סימוני שנדפס בשנת 1937 בצרפת, ובהקלטת אותו עיבוד בפי שרה גורבי בתקליטון בחברת Melotone כנראה קצת לפני שנדפס.
לעיבודו של סימוני נשמרו גם הקלטות פנימיות של קול ישראל (לרבות בנוסח מתוזמר). נוסח הלחן שפרסם סימוני הועתק (בלי הליווי) לאנתולוגיה Chants sephardis שפרסם המוסיקאי ליאון אלגזי בשנת 1958. בשנת 1961 הקליט את השיר רפאל יאיר אלנדב עם שלישיית סלוניקי (רצועה 11 בתקליט Ladino Folk Songs), ובשנת 1969 יהורם גאון בעיבוד דובי זלצר. ההקלטה בפי יהורם גאון היא שהביאה לתפוצתו ולפרסומו של השיר ושימשה בסיס להקלטות רבות מאוד. תרגום מילולי לעברית של "המלך נמרוד" מאת משה אטיאש נדפס בשנת 1961. ככל הידוע אין לשיר זה הקלטות בעברית. 
הביצוע של "המרוקאים" לפיוט "שלום עליכם", הוא עדות שהלחן הותאם לפיוט עוד הרבה לפני ההקלטה בפי יהורם גאון. אפשר להניח שהלחן אומץ לפיוט מן השיר בלדינו, אך ייתכן גם שהיה ללחן זה קיום עצמאי, והוא הותאם לפיוט בלי קשר לשיר בלדינו.