تعرف عبد الحليم لأم كلثوم في بيت أحد معارفه عندما كانت أم كلثوم تزوره لشرب الشاي مع عائلته فأخبر العندليب بقدوم أم كلثم أو الست كما يحلو لمعجبيها تسميتها فأصر العندليب على الحضور فقد كانت أم كلثوم ذلك الوقت من أشهر مطربي مصر بينما لم يكن العندليب قد إشتهر بعد .. فغنى لها وسمعته وأعجبت الست بصوت هذا المطرب الواعد وتوقعت له مستقبلا جيدا.. وبعد سنين عندما إشتهر العندليب وبلغت شهرته جميع أرجاء مصر والوطن العربي بأكمله بدأت الغيرة تدب في نفس كوكب الشرق من هذا المطرب الجديد الذي بدأ يأخذ مكانها في مصر ..
وكان من أكثر ماضايقها شهرة نشيد عبدالحليم الوطني والذي كان يغنيه في 23 يوليو من كل سنة .. و كان النشيد يقدم في حفل ليلي يحضر عامة الشعب كما يحضره الرئيس جمال عبد الناصر ومع أن أم كلثوم تقدم نشيدا أيضا في هذا الحفل الا أنه ومع بزوغ الفجر لاتجد فردا من أفراد الشعب المصري إلا ويردد نشيد العندليب ذلك الذي ملك قلوبهم وسحرهم بصوته الحزين.. فكانت أم كلثوم تغار منه ومن هذا انها قد طلبت من الملحن الكبير كمال الطويل أن يلحن لها ألحان كالتي يعملها لعبدالحليم مما فضح غيرت كوكب الشرق أم كلثوم
من نجاح العندليب الغير اعتيادي.. ومن القصص الطريفة والتي كانت سببا في مشكلة كبيرة بين قطبي الأغنية المصرية.. انه وفي حفل كان يحضره الرئيس عبدالناصرهو نفسه حفل 23 يوليو تم ارجاء صعود العندليب على خشبة المسرح ليكون هو من يختم الحفل بعد أن كانت أم كلثوم هي التي تختمه.. ولكن كوكب الشرق أم كلثوم إستغلت الوضع لصالحها بطريقة ذكية وفيها الكثير من الدهاء فقامت بإطالة أغانيها وإستمرت تغني من الساعة العاشرة مساء حتى الواحدة والنصف بعد منتصف الليل
قاصدةً أن ترهق الجمهور فيبدأ أغلبه في ترك الحفل ولايستمع إلا قلة قليله لذلك العندليب الأسمر الذي كان ينافسها في ذلك الوقت.. مما جعله يخرج للمسرح الساعة الواحدة والنصف فجرا للجمهور وهو في غاية الإنفعال والخوف من أن يذهب الجمهور إلى منازلهم لتأخر الوقت فلايستمع له أحد .. مما حدا به لان يقول لهم (لا ادري اذا كان غنائي بعد السيدة أم كلثوم تكريما لي وشرفا
أم مقلب منها لأن الوقت أصبح متأخرا ) فأخذ الجمهور يصفق بشكل حاد وهم يرددون (معاك للصبح ياحليم) مما رفع معنويات العندليب الأسمر.. ولكن هذا أغضب أم كلثوم فطلبه المشير عبدالحكيم عامر وطالبه بالإعتذار لأم كلثوم عما قاله.. وإستمرت كوكب الشرق غاضبة من العندليب حتى تدخل بعض الأصدقاء المشتركين وأصلحوهم.. ومع المنافسة التي بين أم كلثوم وعبدالحليم إلا انها تأثرت لما علمت بمرضه