Constructed floating wetlands (CFWs) promote the growth of plants in buoyant structures where nutrients can be assimilated into biomass, and thus offer an alternative treatment that is potentially more economically viable than conventional constructed wetlands (CWs). This study examined the hydroponic growth of native Australian plants including Baumea rubiginosa (BR) and Phragmites australis (PA) in a synthetic water mix representing both stormwater and municipal waste water, and their total nitrogen (TN) and total phosphorus (TP) uptake rate over a 35-week period. With increases in the nutrient levels in synthetic waters, the overall dry weight of both roots and shoots, and the accumulated TN and TP values removed from the system, all increased. For both storm and waste waters, BR was found to have a higher overall shoot weight compared to that for the PA. In waters with relatively high nutrient levels, BR was found to have a lower overall root weight compared to that for the PA. The %TN accumulated in all plant root tissue was found to be greater than the shoot tissue and consequently the TN removal efficacy by PA (species with a relatively high growth rate of roots) was high in comparison to that by BR (species with a relatively high growth rate of shoots). The TP removal efficacy by BR was higher than that of PA. These results show that CFWs with native plant species could be used to reduce the nutrients levels in both stormwater and wastewater under a Mediterranean climate condition.