In this article, a novel shifted Gegenbauer operational matrix (SGOM) of fractional derivative in the Caputo sense is derived. Based on this operational matrix, an accurate and effective numerical algorithm is proposed.The SGOM of fractional derivative in conjunction with the tau method are used for solving the constant and variable coefficients space–time fractional telegraph equations (FTE) with various types of boundary conditions, namely,Neumann, Dirichlet and Robin conditions. The convergence analysis of the proposed method is established in $\mathcal L^2_{\omega _\alpha} $. Finally, miscellaneous test examples are given and compared with other methods to clarify the accuracy and efficiency of the presented algorithm.