The slip instability of an earthquake and its abrupt energy release depend primarily on the intensity of strength drop during accelerated fault slip. This process is typically attributed to changes of frictional resistance between two sliding blocks. Here we show that friction changes alone cannot explain observed strength variations of artificial fault zones. Sandstone samples with saw-cut faults and gypsum gouge zones were subjected to many cycles of hold-slide loading. Samples with water-saturated gouge display (1) systematic, time-dependent increase of gouge strength; (2) unstable failure of gouge with large stress drops; and (3) lithification of gouge by crack sealing, recrystallization, porosity reduction, and grain bonding. All these features are absent in identical tests with dry gouge. These observations indicate that gouge particles are cemented by chemical processes during hold periods and suggest that the cyclical strength variations are controlled by cohesion strengthening rather than by friction changes. We further hypothesize that crustal fault zones could be lithified during the interseismic stage, and this lithification would control earthquake-slip instability.