Natural materials, such as nacre and silk, exhibit both high strength and toughness due to their hierarchical structures highly organized at the nano-, micro-, and macroscales. Bacterial cellulose (BC) presents a hierarchical fibril structure at the nanoscale. At the microscale, however, BC nanofibers are distributed randomly. Here, BC self-assembles into a highly organized spiral honeycomb microstructure giving rise to a high tensile strength (315 MPa) and a high toughness value (17.8 MJ m-3), with pull-out and de-spiral morphologies observed during failure. Both experiments and finite-element simulations indicate improved mechanical properties resulting from the honeycomb structure. The mild fabrication process consists of an in situ fermentation step utilizing poly(vinyl alcohol), followed by a post-treatment including freezing-thawing and boiling. This simple self-assembly production process is highly scalable, does not require any toxic chemicals, and enables the fabrication of light, strong, and tough hierarchical composite materials with tunable shape and size.