Nanostructures of carbon-based materials and their composites have been found be the very important class of materials, due to their versatile properties in the field of biomedicine, engineering, optics, water purification, etc. The large surface area, intrinsic conductivity, ability to surface functionalization, biocompatibility, etc. are responsible for the cut-edge performance of carbon-based nanostructures. In past few decades, the carbon nanotubes (CNT), carbon nanodots (CND), graphene, graphite, fullerene (C60), etc. have been efficiently synthesized in the laboratory as well as on industrial scale and have employed them for various applications. This chapter discusses the current status of different contaminant polluting the water system, their effects on human health, and their efficient removal. Out of various modes of water purification, here, advancements in CNTs-based composites have been elaborated. The chemical or biological treatments which can further improve their adsorption properties have also been presented.