Vehicle Anti-lock Braking Systems (ABS) are designed to optimise vehicle braking performance but there are some challenges for their control. One of the challenges is that the optimal slip ratio is difficult to obtain in real time and it can differ under different road conditions. Another challenge is that ABS are non-linear and many of their parameters are difficult to identify in advance. To solve these problems, a new extreme seeking-based adaptive fuzzy sliding mode control strategy is proposed. The proposed Modified Sliding Mode-based Extreme Seeking (MSMES) algorithm is able to avoid the large oscillation and automatically search for the optimal slip ratio. An Adaptive Fuzzy Sliding Mode Controller (AFSMC) is designed to mimic an ideal controller. The simulation results show that the integrated control scheme MSMES-AFSMC is able not only to search for the optimal slip ratio under different road conditions but also has a better braking performance than the conventional COSR for ABS.