Despite water being critical for human survival, its uneven distribution, and exposure to countless sources of pollution make water shortages increasingly urgent. Membrane technology offers an efficient solution for alleviating the water shortage impact. Membranes’ selectivity and permeability can be improved by incorporating additives of different nature and size scales. However, with the vast debate about the environmental and economic feasibility of the common nanoscale materials in water treatment applications, we can infer that there is a long way before the first industrial nanocomposite membrane is commercialized. This stumbling block has motivated the scientific community to search for alternative modification routes and/or materials with sustainable features. Herein, we present a pragmatic review merging the concept of sustainability, nanotechnology, and membrane technology through the application of natural additives (e.g., Clays, Arabic Gum, zeolite, lignin, Aquaporin), recycled additives (e.g., Biochar, fly ash), and recycled waste (e.g., Polyethylene Terephthalate, recycled polystyrene) for polymeric membrane synthesis and modification. Imparted features on polymeric membranes, induced by the presence of sustainable natural and waste-based materials, are scrutinized. In addition, the strategies harnessed to eliminate the hurdles associated with the application of these nano and micro size additives for composite membranes modification are elaborated. The expanding research efforts devoted recently to membrane sustainability and the prospects for these materials are discussed. The findings of the investigations reported in this work indicate that the application of natural and waste-based additives for composite membrane fabrication/modification is a nascent research area that deserves the attention of both research and industry.