We propose a fast solver for the variable-order (VO) time-fractional diffusion equation. Due to the impact of the time-dependent VO function, the resulting coefficient matrix of the large linear system assembling discrete equations of all time levels is a block lower triangular matrix without the block Toeplitz structure. Here, we approximate the off-diagonal blocks by low-rank matrices based on the polynomial interpolation, which can be constructed in O(MlogM) operations with the same number storage requirement, where M is the number of time steps. Furthermore, a divide-and-conquer method is developed to fast solve the approximated linear system. The proposed solver can be implemented in O(NMlogM) complexity with N being the degree of freedom in space. The accuracy of approximation is theoretically studied, and the stability and convergence of the proposed fast method are also investigated. Numerical experiments are carried out to exemplify the accuracy and efficiency of the proposed method.