In Egypt, Lake Manzala is the largest and the most polluted lake due to its use as sink for agricultural drainage, industrial effluents, and sanitary wastes. Pollution indices and associated bacteria of Arthrocnemum macrostachyum were assessed in up and down streams. The concentrations of heavy metal in upstream soil significantly exceeding those in downstream. The highest concentration in upstream soil was recorded by Fe (> 200000 mgkg-1), followed by Al, Mn and Zn (143733.3, 5032.67 and 1036.43 mgkg-1, respectively). Concerning the plant organs, the levels of all elements in root were higher than those in shoot at both up and down streams. The pollution indices of upstream soil were higher than those of downstream for all metals except for Mo. A. macrostachyum has the ability as hyperaccumulator for Al, Fe and V in both up and downstreams and for Cr and Cu in downstream. Plant juice culture media of the halophyte was succeed to develop translucent and slimy colonies. More than 50% of plant juice culture media diluted with upstream water isolates were tolerant to Al, Cr, Cu and Zn at maximum tolerable concentrations 71.26, 12.5, 0.32 and 0.74 mM, respectively. Nine heavy metal-tolerant bacterial isolates were identified according to API microtube systems. Four isolates were matching Burkholderia cepacia, 2 isolates belonged to Providencia retgeri, and the rest isolates referring to Bacillus circulanc, Bacillus lentus and Raoultella ornithinoltica. The study suggests that A. macrostachyum could be classified as an appropriate candidate for phytoremediation efficiency of extremely heavy metal polluted soils.