In this paper, we introduce a new extension of the generalized Apostol-Frobenius-Euler polynomials $\mathcal{H}_n^{[m-1,\alpha]}(x;c,a;\lambda;u)$. We give some algebraic and differential properties, as well as, relationships between this polynomials class with other polynomials and numbers. We also, introduce the generalized Apostol-Frobenius-Euler polynomials matrix $\mathcal{U}^{[m-1,\alpha]}(x;c,a;\lambda;u)$ and the new generalized Apostol-Frobenius-Euler matrix $\mathcal{U}^{[m-1,\alpha]}(c,a;\lambda;u)$, we deduce a product formula for $\mathcal{U}^{[m-1,\alpha]}(x;c,a;\lambda;u)$ and provide some factorizations of the Apostol-Frobenius-Euler polynomial matrix $\mathcal{U}^{[m-1,\alpha]}(x;c,a;\lambda;u)$, which involving the generalized Pascalinebreak matrix.