A series of carboxymethyl starches (CMSs), with various degrees of substitution from 0.1 to 0.79, were synthesized and selected as a model to study the feasibility of using natural polymers as flocculants for oil sand tailings treatment. The flocculation performance of modified CMS in kaolin clay suspensions and oil sand tailings was evaluated in terms of settling rate, solids content, capillary suction time, and specific resistance to filtration of the sediment phase. It was found that the synthesized CMS effectively accelerates settling of kaolin suspensions and oil sand fine tailings, thus demonstrating the feasibility of this application.