The application of microalgal bacteria consortia to the treatment of wastewater is receiving increasing attention, meeting the demand for new green and efficient technologies for water remediation. The specificity of the consortium, however, may strongly affect the performance of the treatment. In fact, even though a general exploitation of the O2/CO2 exchange between microalgae and bacteria is effective, some specific interactions may increase the pollutant removal. With this aim, the co-cultivation of Chlorella protothecoides and Brevundimonas diminuta was tested, with particular attention to the removal capability of nitrogen, phosphorus and chemical oxygen demand (COD) from wastewater. Batch experiments were carried out both for the consortium and, separately, for the bacteria and microalgae alone, in order to compare their performances. B. diminuta showed a remarkable capability for removing organic substances and transforming organic nitrogen to ammonium. C. protothecoides efficiently removed nitrogen and phosphorus. As the specific growth rates of the two organisms are different, the co-cultivation was also carried out also in a continuous system, and the effect of hydraulic retention time (HRT) on the steady-state biomass concentration and nutrient removal efficiency was verified. Residence time was found as the main operating variable for obtaining a significant reduction of pollutants from wastewater.