A bioflocculant-producing bacteria, isolated from sediment samples of a marine environment in the Eastern Cape Province of South Africa demonstrated a flocculating activity above 60% for kaolin clay suspension. Analysis of the 16S ribosomal deoxyribonucleic acid (rDNA) nucleotide sequence of the isolate in the GenBank database showed 99% similarity to Bacillus toyonensis strain BCT-7112 and it was deposited in the GenBank as Bacillus toyonensis strain AEMREG6 with accession number KP406731. The bacteria produced a bioflocculant (REG-6) optimally in the presence of glucose and NH4NO3 as the sole carbon and nitrogen source, respectively, initial medium pH of 5 and Ca2+ as the cation of choice. Chemical analysis showed that purified REG-6 was a glycoprotein mainly composed of polysaccharide (77.8%) and protein (11.5%). It was thermally stable and had strong flocculating activity against kaolin suspension over a wide range of pH values (3–11) with a relatively low dosage requirement of 0.1 mg/mL in the presence of Mn2+. Fourier transform infrared spectroscopy (FTIR) revealed the presence of hydroxyl, carboxyl and amide groups preferred for flocculation. Scanning electron microscopy (SEM) revealed that bridging was the main flocculation mechanism of REG-6. The outstanding flocculating performance of REG-6 holds great potential to replace the hazardous chemical flocculants currently used in water treatment.