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

המילה כרם מצויה בכמה שמות יישובים בארץ. במקרא נזכר יישוב בשם בית הכרם (למשל בירמיהו ו, א) ויש המזהים אותו עם עין כרם במערב ירושלים. במשנה נזכרת בקעת בית כרם, בקעה רחבה ופורייה בגבול שבין הגליל התחתון לגליל העליון, ואומנם באותו אזור נמצא הכפר מַגְ'ד אל־כֻּרוּם (מילולית: מֶגֶד הכרמים), שככל הנראה משמר שם עברי קדום, וכן העיר החדשה כַּרְמִיאֵל.