This survey was conducted on 4 tribes (Ababda, Bisharia, Nubian, and Rashayda) living in the south of the Nile and the Eastern Desert of Egypt to document and compare the traditional herbal medicines and assess the relationships among these tribes depending on their ethnobotanical utilization. A total of 180 interviews were conducted with the Bedouins and herb healers, 45 informants for each tribe within the different age group of 18–85 years. Thirty-nine species belonging to 36 genera and 27 families were utilized. Fabaceae, Poaceae, and Rutaceae were species-rich families. The species comprised 43.6% wild, 38.5% cultivated, and 17.9% bought from herbalist shops. The leaves were the most used parts (31%), followed by stems and fruits with 22% each. Distinct species included Acacia nilotica which is used in the treatment of dental pain with a use-value of 33.3%, Cymbopogon schoenanthus subsp. proximus in treatment of both cough or headache with use values 35 and 30.6% and a combination of Acacia nilotica with Lawsonia inermis in the treatment of sore throat with use-value 22.2%. The highest similarity, based on the ethnobotanical treatments, was recorded between the Nubian and Rashayda tribes (55.3%) followed by the similarity between Ababda and Bisharia is 46.8%. Diarrhea and headache were the most common diseases with 7 different recipes, whereas cough and dental pains have 6 recipes. this type of research must be promoted to understand the potential utilization of the prevalent flora in the human healthcare