Mangroves, dominating tropical intertidal zones and estuaries, are among the most salt tolerant plants, and propagate through reproductive units called propagules. Similarly to plant seeds, propagules may harbor beneficial bacteria. Our hypothesis was that mangroves, being able to grow into seawater, should harbor bacteria able to interact with the host and to exert positive effects under salt stress, which could be exploited to improve crop production. Therefore, we isolated bacterial endophytes from mangrove propagules with the aim to test whether these bacteria have a beneficial potential on their natural host and on different crops such as barley and rice, cultivated under salt stress. The 172 bacterial isolates obtained were screened for plant growth promotion (PGP) activities in vitro, and the 12 most promising isolates were tested on barley under non-axenic conditions and salt stress. Gordonia terrae KMP456-M40 was the best performing isolate, increasing ear weight by 65%. Based on the in vivo PGP activity and the root colonization ability, investigated by fluorescence in situ hybridization and confocal microscopy, three strains were additionally tested on mangrove propagule germination and on rice growth. The most effective strain was again G. terrae KMP456-M40, which enhanced the root length of mangrove seedlings and the biomass of salt-stressed rice under axenic conditions up to 65% and 62%, respectively. We demonstrated that propagules, the reproductive units of mangroves, host beneficial bacteria that enhance the potential of mangrove seedlings establishment and confer salt tolerance to cereal crops.