The capacity of macro-algae to remove nutrients means they have the potential to concomitantly bioremediate polluted waters and generate exploitable biomass. The influence of different nitrogen (N) regimes on growth, biochemical composition and bioremediation capacity was studied for two species of the macro-alga Cladophora. These were incubated in media containing four single N sources, ammonium (NH4+), nitrite (NO2−), nitrate (NO3−) and urea (CO(NH2)2), each with four nitrogen/phosphorous (N/P) ratios, followed by equimolar dual mixtures of these N sources at two selected N/P ratios. There were clear differences in growth between species, depending upon the nutrient regime. In every instance, the daily growth rate (DGR) of Cladophora parriaudii (4.75–11.2%) was higher than that of Cladophora coelothrix (3.98–7.37%) with significance when either NO2− (p = 0.025) or urea (p = 0.002) were the employed N form. Differences in algal productivity were reflected in the corresponding N-uptake, whereby C. parriaudii consistently removed more N than C. coelothrix. There were significant differences in growth (p = 0.005) when C. parriaudii was cultivated in a single and multi-N source medium: NH4+ was preferentially removed from the medium, whereas urea was typically removed secondarily. However, the presence of urea in the medium enhanced the uptake of the other co-existing N forms and resulted in an increased DGR and yielded a biomass rich in carbohydrates. The relative composition of C. parriaudii varied depending upon N/P ratio of the medium, with the final proportion of protein and carbohydrate ranging from 5 to 15% and 36 to 54% per unit dry weight, respectively. Results from this study demonstrated that algal strain selection is key to treating waste-streams with specific N profiles. Additionally, the biochemical profile of the biomass produced is dependent on the alga and the N regime, providing the potential for designing processes with specific properties and products.