The objective of this research was to determine the combined effects of ethylenediaminetetraacetic acid (EDTA) and plant growth-promoting rhizobacteria (PGPR) on the phytostabilization of Cd, Pb, and Zn by corn and chemical fractionation of these elements in soil. Three heavy metal-resistant bacteria (P18, P15, and P19) were selected. All strains, belonging to the fluorescent pseudomonads, exhibited plant growth-promoting properties, including phosphorus solubilization and production of siderophore, indole acetic acid, and 1-aminocyclopropane-1-carboxylic acid deaminase. Applying EDTA individually or in combination with bacterial strains (P18 and P15) significantly increased shoot biomass. The highest dry shoot biomass was recorded in the combined treatment of EDTA and P15-inoculated pots. Application of EDTA in PGPR-inoculated pots increased concentrations of heavy metals in corn shoots and roots compared to the control. The highest concentration of Zn in corn root and shoot was observed in P15 + EDTA treatment, which were 2.0-fold and 1.3-fold higher than those in the untreated soil. Results of chemical speciation showed that the co-application of EDTA and fluorescent pseudomonads strains increased the bioavailability of Zn, Pb, and Cd by their redistribution from less soluble fractions to water-soluble forms. It was concluded that bacterial inoculation could improve the efficiency of EDTA in phytostabilization of heavy metals from multi-metal contaminated soils.