To achieve the co-production of H2 and CH4, co-digestion of food waste (FW) and paper waste (PW) was performed on the recirculated two-phase anaerobic digestion (R-TPAD). The PW content in the feedstock increased from 0% to 20%, 40% and 50% (in total solids) with FW as the rest. The results showed that bioH2 and bioCH4 were simultaneously and stably produced in the long-term operation. With the increasing PW content, the removal efficiency of volatile solids decreased slightly from 84.9% to 78.4%; the bioH2 yields increased from 50 to 79 NL-H2/kg-VSfed while the bioCH4 yields decreased from 426 to 329 NL-CH4/kg-VSfed. With the fixed amount of FW, adding PW could significantly increase the total bioenergy yields. The relative abundance showed that the key H2-producing bacteria, Caproiciproducens and Thermoanaerobacterium, increased after PW addition. The microbial distribution suggests that the H2-producers were recirculated to the first stage after proliferating in the second stage.