A combination of microalgae (Chlorella vulgaris or C. sorokiniana) and a microalgae growth-promoting bacterium (MGPB, Azospirillum brasilense strain Cd), co-immobilized in small alginate beads, was developed to remove nutrients (P and N) from municipal wastewater. This paper describes the most recent technical details necessary for successful co-immobilization of the two microorganisms, and the usefulness of the approach in cleaning the municipal wastewater of the city of La Paz, Mexico. A. brasilense Cd significantly enhanced the growth of both Chlorella species when the co-immobilized microorganisms were grown in wastewater. A. brasilense is incapable of significant removal of nutrients from the wastewater, whereas both microalgae can. Co-immobilization of the two microorganisms was superior to removal by the microalgae alone, reaching removal of up to 100% ammonium, 15% nitrate, and 36% phosphorus within 6 days (varied with the source of the wastewater), compared to 75% ammonium, 6% nitrate, and 19% phosphorus by the microalgae alone. This study shows the potential of co-immobilization of microorganisms in small beads to serve as a treatment for wastewater in tropical areas.