This research evaluates process instability together with microbial population dynamics of the startup of an anaerobic digestion of a mild pretreated solid olive oil waste. The pretreatment consisted of a mild thermal treatment called thermo-malaxation and a subsequent dephenolized process of the olive mill solid waste. The anaerobic digestion process of the mild pretreated and partially dephenolized biomass was studied for three Hydraulic Retention Times (HRTs), with 21 days each HRT, with an organic load rate of 1 g VS/L d, carried out at mesophilic temperature (35 ± 1 °C). The average value of methane yield decreased from 204 ± 9 mL CH4/g VS d on day 21, the last day of the first HRT, to 87 ± 24 mL CH4/g VS d on day 60, the last day of the third HRT. The alkalinity decreased drastically, indicating instability of the anaerobic digestion process. Although phenolic compounds were partially extracted in the pretreatment, the observed increase in phenolic compounds during reactor operation might be contributed to the methane production decay. Interestingly, volatile fatty acids decreased with time, indicating that not only the methanogenic stage but also the hydrolysis stage was affected. Indeed, the microbial analysis showed that the abundance of hydrolytic bacteria decreased over time. It is also worth noticing that hydrogenotrophic methanogens, while present during the first two HRTs, were not observed at the end of the last HRT. This observation, together with the increase in the relative abundance of acetoclastic methanogens, showed a shift in the methane production pathway from hydrogenotrophic methanogenesis to acetotrophic methanogenesis.