Time spectral methods approximate the solution of a differential equation by a combination of certain basis functions (e.g.polynomials), which is a natural companion of spectral discretization in space. It produces highly accurate numerical results in time, but all the combination coefficients must be computed in one-shot by solving an all-at-once system. This system is of Kronecker tensor form between the time and space matrices, where the matrix arising from the time spectral methods, denoted by M, is a non-structured matrix which brings significant challenges for practical computation. In this paper, we propose an efficient preconditioner for the all-at-once system which permits well-conditioned diagonalization and thus each preconditioning step can be solved in an efficient time parallel manner. The spectral analysis of preconditioned matrix reveals highly clustering of the eigenvalues, promoting rapid convergence of the GMRES method. The preconditioner is obtained by a novel factorization of M and then a replacement of the Toeplitz matrices in such a factorization by the corresponding \alpha-circulant matrix of Strang-type. We illustrate such a factorization for the Legendre dual-Petrov-Galerkin method and for other widely used time spectral methods it holds as well.