Natural organic coagulants (NOCs) such as chitosan and Moringa oleifera seeds have been extensively characterized for potential application in water treatment as an alternative to metal-based coagulants. However, the action of both chitosan and M. oleifera seeds is mainly restricted to anionic organic pollutants because of their cationic functional groups affording poor cationic pollutant coagulation by electrostatic repulsion. In this study, we employed ethanolic grape seed extract (GSE) and grape seed-derived polyphenols such as tannic acid and catechin in an effort to find novel NOCs showing stable anionic forms for removal of cationic organic pollutants. The target substances tested were malachite green (MG) and crystal violet (CV), both mutagenic cationic dyes. Polyphenol treatment induced fast decolorization followed by gradual floc formation concomitant with red or blue shifts in maximum absorbance wavelengths of the cationic dyes. Liquid chromatography analysis of flocs formed by polyphenols directly showed that initial supramolecular complexes attributed mainly to electrostatic attraction between polyphenol hydroxyphenyl groups and cationic dyes further progressed into stronger aggregates, leading to precipitation of dye-polyphenol complexes. Consistent with the results obtained using catechin and tannic acid, use of GSE also resulted in effective decolorization and coagulation of soluble MG and CV in aqueous solutions. Screening of several organic GSE components for NOC activity strongly suggested that natural polyphenols are the main organic ingredients causing MG and CV removal via gradual floc formation. The treatment by natural polyphenols and GSE decreased toxicity of MG- or CV-contaminated water.