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

יעקב אורלנד העיד על חיבור השיר עדויות שונות, ותואמות באופן חלקי בלבד:

בריאיון לציפי פליישר, 10.2.1963 ("התפתחותו ההיסטורית של שיר העם העברי" [1964], עמ' 376):

"הייתי באיזו חתונה של צעירה בוכרית בירושלים ושם שרו את הנעימה [שר את החלק הראשון] ולא ידעתי מה זה בבוכרית. שאלתי מישהו והוא אמר לי שזה שיר אהבה: "אני אוהב אותך, את אוהבת אותי". מצאה חן בעיניי המנגינה וחיברתי את המילים "עץ הרימון", לפי המנגינה ולא לפי העיבוד שידוע היום. זה היה קצת מונוטוני ואחר-כך כעבור שבוע ימים נפוץ השיר בכל הארץ . . . אחר-כך, כשהשיר כבר היה ידוע מאוד הפיצו אותו רבים, חנה רובינא שהפיצה אותו בין החיילים בתקופת הבריגדה. אחר-כך לקח את זה אדמון (גורוכוב) והוא הוסיף לזה כדי שלא יהיה מונוטוני עוד משהו, זה היה לאחר מספר שנים. זה היה בסוף שנות השלושים 1937-1938 [מתייחס  לכתיבת החלק הראשון]. בשנות המלחמה, כשחנה רובינא שרה את השיר בין החיילים באיטליה, היא עוד שרה אותו לפי הנוסח הראשון. רק אחר-כך אדמון חיבר לזה [קטע] שני . . . השיר כמו שהוא ידוע היום . . . הוא השיר השלם, ולכן הוא כבר יותר קצר, ובמקום שישה בתים  (כל הזמן אותה המנגינה, כפי שהיה בהתחלה) יש עכשיו כאילו שלושה בתים, והשיר יוצא יותר קצר.

בספר "היו לילות - שירי הזמר של יעקב אורלנד" (1985, עמ' 150) מובאת העדות הבאה:

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

כתבים מאוחרים של אורלנד טוענים כי "עֵץ הָרִמּוֹן נָתַן לֵחוֹ".

לביצועים נוספים:

• משה אויסטר (Moishe Oysher)
• רן אלירן
• עפרה חזה (סרטון)
• רוחמה רז (סרטון)
• לירון לב (סרטון מערב שירי אורלנד וזעירא בפסטיבל עין-גב 2009)
• רוזה וול (Rosa Wol) (סרטון)
• אריק לביא
• אריק איינשטיין
• יזהר כהן
• זהבה בן
• גלית גיאת
• אברהם פררה
• אורי שבח (סרטון, מתוך החלק הלא תחרותי בפסטיבל הזמר המזרחי 1975)
• רביעיית הדר נויברג (סרטון)
• ליאת יצחקי
• לירון לב ורבקה זוהר - לצפייה ולהאזנה באיכות אולפן
• שי טרי (במסגרת "כיתת השיר הישראלי" בהדרכת שמעון כהן, אפריל 2015)

ראו גם:

• ביאור לשיר מאת משה פלאם במאגר ויקיטקסט
• "פעם אחת תקעתי נאד", גרסה היתולית לשיר
• בזמן מלחמת המפרץ, כתב דב ליכטנברג לפי הלחן את השיר "טילי הסקאד" (מתועד בכרטסת מאיר נוי)