Blue-green algae (BGA) are unique photosynthetic prokaryotes which are associated with heterotrophic bacteria. BGA together with the associated heterotrophic bacteria (AHB) play a distinct role in soil and plant development. Despite the high diversity of the BGA-AHB, little is known about their potential ecological role. Thus, the present study aimed to obtain and identify BGA and their cultivable AHB. Two nitrogen-fixing BGA were isolated from desert soil and identified as Anabaenopsis circularis strain AnHu and Nostoc sp. strain NoHu. Based on the colony morphology, 51 and 12 BGA-AHB isolates were obtained from AnHu and NoHu, respectively, and screened for plant growth-promoting activities (PGPAs). Ten promising BGA-AHB isolates that displayed multifunctional ability were further identified. The analysis revealed that the 6 and 4 identified AnHu- and NoHu-AHB isolates, were affiliated to 4 and 2 different phyla, respectively, indicating high diversity of cultivable BGA-AHB. Moreover, the analysis revealed sequence identity for some BGA-AHB with a newly described strain, such as Pseudomonas songnenensis. The identified BGA-AHB isolates showed identical sequences with NCBI strains known for their functionality as plant growth-promoters (PGPs) under harsh environmental conditions. Our results suggest that BGA-AHB are useful as an opulent source for PGPs in Egyptian agricultural arid soil.