The use of laminated composite materials have exponentially increased over the last four decades spanning both aviation and military industries. Failure theories for an orthotropic layer under multi-axial and combined stress states have been extensively investigated and many macro-failure theories have been proposed. Current failure criteria share the use of stress or strain invariants for the homogenized medium in order to generate failure envelopes in the stress or strain space, e.g Hashin[5,6], Tsai and Wu[10], Puck[9], Christensen [3], among several others. In fact, it has been previously argued, e.g. Hashin[5,6], that the complexity of microstructural damage offer little or no hope for using micro-mechanical methods for failure prediction of composite materials. However, the recent advances in computational nonlinear methods allow the use of failure prediction based on the invariants of the average stress and strain in the matrix and fiber phases, e.g the SIFT[4] criteria. This study deals with using the high fidelity generalized method of cells (HFGMC) micromechanical method, Aboudi[1,2], and its nonlinear and parametric extensions, Haj-Ali and Aboudi [7,8], in order to predict ultimate failure of fiber composite media. Continuum damage constitutive models are implemented for the fiber and matrix subcells in order to generate the effective softening behavior. The formulation and the computational implementations will be discussed. The HFGMC failure envelops will be shown compared to some well-known failure criteria. Future use and implementation of the proposed damage approach will be also explored.