This work firstly investigated the suitable organic loading (OL) and feed to inoculum (F/I) ratio of three kinds of tobacco stalks (TS116, TS99, and TS85) during anaerobic digestion (AD) via response surface methodology (RSM). The highest experimental methane yield (EMY) of 148.1 mL/g VS was achieved from TS116 at OL of 20.2 g VS/L and F/I ratio of 1.1. To further increase EMY, various pretreatments including alkaline hydrogen peroxide (AHP), NaOH, KOH, Ca(OH)2, HCl, and oxalic acid (H2C2O4) were implemented on TS116. Results showed that AHP was most effective, and the maximal EMY of 350.7 mL/g VS and biodegradability (Bd) of 81.4% were obtained from 7% AHP pretreated TS116, which increased by 105.6% than untreated. XRD, FTIR, and SEM analyses evidenced that the structure of AHP pretreated TS116 was strongly disrupted. This study lays the foundation for applying this waste into AD in future applications.