On the development of flexible electronics, a highly flexible nonvolatile memory, which is an important circuit component for the portability, is necessary. However, the flexibility of existing nonvolatile memory has been limited, e.g. the smallest radius into which can be bent has been millimeters range, due to the difficulty in maintaining memory properties while bending. Here we propose the ultra flexible resistive nonvolatile memory using Ag-decorated cellulose nanofiber paper (CNP). The Ag-decorated CNP devices showed the stable nonvolatile memory effects with 6 orders of ON/OFF resistance ratio and the small standard deviation of switching voltage distribution. The memory performance of CNP devices can be maintained without any degradation when being bent down to the radius of 350 μm, which is the smallest value compared to those of existing any flexible nonvolatile memories. Thus the present device using abundant and mechanically flexible CNP offers a highly flexible nonvolatile memory for portable flexible electronics.