Paper-based biosensors are considered simple and cost-efficient sensing platforms for analytical tests and diagnostics. Here, a paper-based electrochemical biosensor was developed for the rapid and sensitive detection of microRNAs (miRNA-155 and miRNA-21) related to early diagnosis of lung cancer. Hydrophobic barriers to creating electrode areas were manufactured by wax printing, whereas a three-electrode system was fabricated by a simple stencil approach. A carbon-based working electrode was modified using either reduced graphene oxide or molybdenum disulfide nanosheets modified with gold nanoparticle (AuNPs/RGO, AuNPs/MoS₂) hybrid structures. The resulting paper-based biosensors offered sensitive detection of miRNA-155 and miRNA-21 by differential pulse voltammetry (DPV) in only 5.0 µL sample. The duration in our assay from the point of electrode modification to the final detection of miRNA was completed within only 35 min. The detection limits for miRNA-21 and miRNA-155 were found to be 12.0 and 25.7 nM for AuNPs/RGO and 51.6 and 59.6 nM for AuNPs/MoS₂ sensors in the case of perfectly matched probe-target hybrids. These biosensors were found to be selective enough to distinguish the target miRNA in the presence of single-base mismatch miRNA or noncomplementary miRNA sequences.