We propose a fast algorithm for the variable-order (VO) space-fractional advection-diffusion equations with nonlinear source terms on a finite domain. Due to the impact of the space-dependent the VO, the resulting coefficient matrices arising from the finite difference discretization of the fractional advection-diffusion equation are dense without Toeplitz-like structure. By the properties of the elements of coefficient matrices, we show that the off-diagonal blocks can be approximated by low-rank matrices. Then we present a fast algorithm based on the polynomial interpolation to approximate the coefficient matrices. The approximation can be constructed in O(kN) operations and requires O(kN) storage with N and k being the number of unknowns and the approximants, respectively. Moreover, the matrix-vector multiplication can be implemented in O(kNlog N) complexity, which leads to a fast iterative solver for the resulting linear systems. The stability and convergence of the new scheme are also studied. Numerical tests are carried out to exemplify the accuracy and efficiency of the proposed method.