Accelerated eutrophication is one of the most serious problems confronting freshwater systems worldwide. More effective methods to reduce nutrients from eutrophic water with high nitrogen but low carbon source are now urgently needed. In this study, the methods of floating plant remediation and aerobic denitrification were combined for seeking an effective strategy. Four aerobic denitrifying bacteria were adopted. Each strain was co-cultured with Eichhornia crassipes, and then the effects of different combinations on the removal of nitrogen and phosphorus were compared. Meanwhile, their impacts on the growth and physiological characteristics of plants were also measured. The results showed that the association of aerobic denitrifying bacteria with E. crassipes was effective in enhancing the simultaneous removal of nitrogen and phosphorus. E. crassipes helped bacteria to eliminate the accumulation of nitrites under the condition of limited carbon sources. Cooperation between Rhizobium rosettiformans and E. crassipes exhibited the best remediation performance. The four aerobic denitrifying bacteria increased the plant growth and phosphorus content, and had different effects on the plant root activity, leaf chlorophyll, leaf soluble sugar and leaf soluble protein concentration. Although the overall nutrients removal efficiency was greatly improved by the synergic association, the percentage contribution of plant uptake remained constant.