Polymers have gained gradual attention in soil stabilization as a sustainable alternative to inorganic counterparts such as cement. However, the effects of polymers on the strength of soils and soil-waste mixtures are still unclear. Meanwhile, waste recycling has been important in fostering a sustainable environment in recent decades. To solve the deficiency in knowledge, large-strain strength of polymer-modified kaolinite (KA) and Class-F fly ash–kaolinite mixtures (FAKAs) was investigated with isotropically consolidated undrained triaxial compression tests. Both synthetic polymer (polyethylene oxide, PEO) and naturally occurring biopolymers (chitosan and xanthan gum) were used. An interface model was also proposed to account for interfaces of KA, FAKA, and fly ash. Experimental results suggested that (1) polymers induce preexisting fabrics to render dilative behavior to KA and FAKA; (2) normal consolidation lines (NCLs) and critical state lines (CSLs) for polymer-modified KA were nearly parallel to each other, while the CSLs were steeper than NCLs for polymer-modified FAKA, possibly due to kaolinite filling the voids of crushed fly ash cenospheres; (3) the critical state friction angle () of kaolinite increased from 19.7° to 24.1° and 22.3° with the addition of PEO and chitosan via mechanisms of polymer bridging and charge neutralization, respectively; xanthan gum decreased the of kaolinite to 19.1° via Coulombic repulsion; and (4) the just mentioned mechanisms held for polymer-modified FAKA to a lesser extent due to other complicated interactions, such as polymer crosslinking or entanglement and ion-dipole interactions.