Generally, solving linear systems from finite difference alternating direction implicit scheme of two-dimensional time-space fractional differential equations with Gaussian elimination requires O(NM1M2(M12+M22+NM1M2)) complexity and O(NM12M22) storage, where N is the number of temporal unknown and M, M are the numbers of spatial unknown in x, y directions respectively. By exploring the structure of the coefficient matrix in fully coupled form, it possesses block lower-triangular Toeplitz structure and its blocks are block-dense Toeplitz matrices with dense-Toeplitz blocks. Based on this special structure and cooperating with time-marching or divide-and-conquer technique, two fast solvers with storage O(NMM) are developed. The complexity for the fast solver via time-marching is O(NMM(N+ log(MM))) and the one via divide-and-conquer technique is O(NMM(logN+ log(MM))). It is worth to remark that the proposed solvers are not lossy. Some discussions on achieving convergence rate for smooth and non-smooth solutions are given. Numerical results show the high efficiency of the proposed fast solvers.