Surface modification of cellulose-based paper, which displays roll-off properties for water and oils (surface tension >= 23.8 mN.m(-1)) and good repellency toward n-heptane (20.1 mN.m(-1)), is reported. Droplets of water, diiodomethane, motor oil, hexadecane, and decane all "bead up", i.e., exhibit high contact angles, and roll off the treated surface under the influence of gravity. Unlike widely used approaches that rely on the deposition of nanoparticles or electrospun nanofibers to create superamphiphobic surfaces, our method generates a hierarchical structure as an inherent property of the substrate and displays good adhesion between the film and substrate. The two-step combination of plasma etching and vapor deposition used in this study enables fine-tuning of the nanoscale roughness and thereby facilitates enhanced fundamental understanding of the effect of micro- and nanoscale roughness on the paper wetting properties. The surfaces maintain their "roll-off' properties after dynamic impact tests, demonstrating their mechanical robustness. Furthermore, the superamphiphobic paper has high gas permeability due to pore-volume enhancement by plasma etching but maintains the mechanical flexibility and strength of untreated paper, despite the presence of nanostructures. The unique combination of the chemical and physical properties of the resulting superamphiphobic paper is of practical interest for a range of applications such as breathable and disposable medical apparel, antifouling biomedical devices, antifingerprint paper, liquid packaging, microfluidic devices, and medical testing strips through a simple surface etching plus coating process.