Cellulose, the main component of plant cell walls, is degradable in nature. However, to the best of our knowledge, this is the first report that compares the biodegradability of cellulose fibers with different structures in natural waters. River water, brackish water, and seawater were collected from the Kamo River and Osaka Bay, Japan. Biodegradation of cellulose fibers with different structures and crystallinities, ramie, mercerized ramie, and regenerated cellulose fibers in the collected natural water was investigated in the dark at 20 °C for 30 days. The primary and aerobic ultimate biodegradability were evaluated by weight loss and biochemical oxygen demand (BOD) tests, respectively. In the weight-loss test, cellulose fibers were found to be degraded by more than 50% in any natural water within 30 days. However, in the BOD test, biodegradation was diminished, with values of 40%, 20–30%, and 2–10% in river water, brackish water, and seawater, respectively. These results indicate that cellulose fibers are easily degraded into fine fragments, but it is difficult to cause their ultimate decomposition into water and carbon dioxide. Existence of such a tendency in the degree of biodegradation among the cellulose fibers remains unclear. The molecular weight of cellulose fibers in natural water was also measured during their degradation. The degradation behavior in river water and seawater was observed to be different from that in brackish water. The results thus obtained indicate that the microorganisms and enzymes that degrade cellulose fibers differ depending on the natural water, which influences the degree and mechanism of biodegradation.