This work demonstrates a novel-type paper-based solid electrolyte (PBSE) and its application in Al-air battery, which is targeted for miniwatt applications. Benefited from the solid-form electrolyte, a liquid-free operation of the Al-air battery is realized, eliminating the potential leakage hazard and therefore improving the battery practicability. The PBSE is prepared by impregnating gel electrolyte into porous cellulose paper, followed by a solution casting process to solidify the gel. The as-prepared PBSE can either be used in mechanical rechargeable Al-air batteries, or be integrated into single-use flexible Al-air batteries. Currently the PBSE can achieve a moderate battery performance with a peak power density of 3.8 mW cm-2 and an Al specific capacity of 900.8 mA h g-1. Properties of the PBSE can be further improved by a comprehensive parametric study on its fabrication parameters, such as gel concentration, casting temperature, casting time, porosity and pore size of paper substrate, etc.