Al-air batteries are generally fabricated by rigid and heavyweight materials such as metal or plastic, meanwhile a bulky electrolyte solution either in static or circulation is requisite to ensure their steady operation. Therefore, they are less suitable for powering flexible and portable devices with lower power demand, such as wearable electronics, point-of-care test assays, RFID tags, etc. This work develops a flexible and lightweight Al-air battery with much less electrolyte storage, which is totally fabricated on a cellulose paper. The Al foil anode is embedded inside the paper substrate during paper-making process, while the air-breathing cathode is deposited onto the paper surface using an oxygen reduction ink. Despite its simple structure and low cost, this flexible Al-air battery can deliver a satisfactory power density of 19 mW cm−2 with alkaline electrolyte, and its operation lifespan is as long as 58 h with only 25 mg Al when saline electrolyte is employed. The corresponding Al specific capacity is as high as 2338 mA h g−1. In addition, this battery exhibits an excellent flexibility when facing different bending angles from 60 to 180° and multiple bending times greater than 1000. Furthermore, a flexible current or voltage output can be easily obtained by scaling up or stacking the present flexible Al-air battery, respectively, and the corresponding stacking efficiency is as high as 94%. In the future, non-metal oxygen catalyst will be employed to improve its environmental friendliness, and hot-pressing will be adopted to further increase its robustness to external deformation.