This paper considers two methods for speeding-up stochastic local search SAT procedures. The first method aims at using the search history (represented by additional formulas derived at every state of the search process) to constrain the selection of candidate variables used to navigate through the search space of truth-value assignments. The second method uses the search history to allow multiple modifications of the current truth-value assignment in a single search step. Empirical studies of these two methods have demonstrated their effectiveness on structured and industrial SAT instances.