This study investigated the temporal dynamics of digestion efficiency and community stability in digesters fed with waste activated sludge (WAS), straw (STR-AD), food waste (FW-AD) and mixture of straw-and-food waste (STR-FW-AD). Results showed that carbon removals of recalcitrant substrates (i.e., 48.2 ± 3.9% in WAS-AD and 57.8 ± 4.9% in STR-AD) were lower than that of labile substrates (i.e., 70.7 ± 4.0% in FW-AD). Nonetheless, carbon removal of recalcitrant substrates was largely improved through co-digestion (70.3 ± 3.2% in STR-FW-AD). In contrast to monopoly communities (e.g., the highly enriched Paludibacter) fed with the labile substrates, recalcitrant substrates supported highly diverse communities. Accordingly, the medians of negative/positive cohesions of communities in WAS-AD, STR-AD, STR-FW-AD and FW-AD decreased from 0.86 to 0.63, suggesting their decreasing community stability. Microbial source tracking analyses showed the major contribution of the STR-AD community to the co-digestion community. This study provided unprecedented mechanistic insight into stability improvement of substrate co-digestion on the methanogenic digestion microbiome.