For improving bending toughness and fatigue performance of brittle cement-based composites, two types of water-soluble polymers (such as dispersible latex powder and polyvinyl alcohol powder) and waste tire-rubber powders are added to concrete as admixtures. Multiscale toughening mechanisms of these additions in concretes were comprehensively investigated. Four-point bending fatigue performance of four series concretes is conducted under a stress level of 0.70. The results show that the effects of dispersible latex powder on bending toughness and fatigue life of concrete are better than those of polyvinyl alcohol powder. Furthermore, the bending fatigue lives of concrete simultaneously containing polymers and waste rubber powders are larger than those of concrete with only one type of admixtures. The multiscale physics-chemical mechanisms show that high bonding effect and high elastic modulus of polymer films as well as good elastic property and crack-resistance of waste tire-rubber powders are beneficial for improving bending toughness and fatigue life of cementitious composites.