There have been numerous studies that have aimed at improving the low tensile strength, stiffness, and toughness of cementitious materials. This study aims to show that all of these characteristics can be greatly improved by the addition of ladder scale reinforcement at the nano and micro scale. Carbon nanofibers (CNFs) as well as polyvinyl alcohol (PVA) microfibers were used as reinforcement. The mechanical properties of the nanocomposites were investigated by fracture mechanics three-point bending test. The microstructure and the morphology of nanocomposite samples were studied using an ultra high resolution scanning electron microscope (SEM). The results clearly illustrate that the incorporation of nanofibers and microfibers greatly improves the flexural strength, Young's modulus, and toughness of the cement matrix.