<p>In this paper, we consider the determinant evaluation of a generalized comrade matrix based on a novel incomplete block-diagonalization approach which transforms the determinant of the original generalized comrade matrix into the determinants of tridiagonal matrices and comrade matrix with lower-order. Then, a breakdown-free recursive algorithm for computing the determinant of the generalized comrade matrix is proposed. Even though the algorithm is not a symbolic algorithm, it never suffers from breakdown. Furthermore, we propose an explicit formula for the determinant of the generalized comrade matrix with quasi-Toeplitz structure. Some numerical results with simulations in MATLAB implementation are provided to demonstrate the accuracy and effectiveness of the proposed algorithm, and its competitiveness with MATLAB built-in function.</p>