In this paper, we present an accelerated gradient-based iterative algorithm for solving extended Sylvester–conjugate matrix equations. The idea is from the gradient-based method introduced in Wu et al. (Applied Mathematics and Computation 217(1): 130–142, 2010a) and the relaxed gradient-based algorithm proposed in Ramadan et al. (Asian Journal of Control 16(5): 1–8, 2014) and the modified gradient-based algorithm proposed in Bayoumi (PhD thesis, Ain Shams University, 2014). The convergence analysis of the algorithm is investigated. We show that the iterative solution converges to the exact solution for any initial value provided some appropriate assumptions be made. A numerical example is given to illustrate the effectiveness of the proposed method and to test its efficiency and accuracy compared with an existing one presented in Wu et al. (2010a), Ramadan et al. (2014) and Bayoumi (2014).