Cellulose nanofibers (Cel-F) were extracted by a simple and harmless Star Burst (SB) method, which produced aqueous cellulose-nanofiber solution just by running original cellulose beads under a high pressure of water in the synthetic SB chamber. By optimizing the SB process conditions, the cellulose nanofibers with high aspect ratios and the small diameter of ∼23 nm were obtained, which was confirmed by transmission electron microscopy (TEM). From the structural analysis of the Cel-F/PVA composite by the scanning electron microscopy (SEM), it was found that the Cel-F were homogeneously dispersed in the PVA matrix. Considering the high molecular compatibility of the cellulose and PVA due to the hydrogen bonding, a good adhesive interface could be expected for the Cel-F and the PVA matrix. The influences of the morphological change in Cel-F on the mechanical properties of the composites were analysed. The Young’s modulus rapidly increased from 2.2 GPa to 2.9 GPa up to 40 SB treatments (represented by the unit Pass), whereas the Young’s modulus remained virtually constant above 40 Pass. Due to the uniform dispersibility of the Cel-F, the Young’s modulus of the 100 Pass composite at the concentration of 5 wt% increased up to 3.2 GPa. The experimental results corresponded well with the general theory of the composites with dispersed short-fiber fillers, which clearly indicated that the potential of the cellulose nanofibers as reinforcement materials for hydrophilic polymers was sufficiently confirmed.