In this paper, a relaxed gradient based algorithm for solving extended Sylvester-conjugate matrix equations by considering a relaxation parameter is proposed. The convergence analysis of the algorithm is investigated. Theoretical analysis shows that the new method converges under certain assumptions. A numerical example is given to illustrate effectiveness of the proposed method and to test its efficiency compared with an existing one.