This work investigates systematically strain localization and failure mechanics for elastoplastic damage solids. Two complementary methodologies, i.e., traction-based discontinuities localized in an elastic solid and strain localization of a stress-based inelastic softening solid, are addressed. In the former it is assumed a priori that the discontinuity (band) forms with a continuous stress field and along the known orientation. A traction-based failure criterion is introduced to characterize the discontinuity (band) and the orientation is determined from Mohr’s maximization postulate. If the (apparent) displacement jumps are retained as independent variables, the strong/regularized discontinuity approaches follow, requiring constitutive models for both the bulk and discontinuity (band). Elimination of the displacement jumps at the material point level results in the embedded/smeared discontinuity approaches in which an overall inelastic constitutive model fulfilling the static constraint suffices. The second methodology is then adopted to check whether the assumed strain localization can occur and identify its consequences on the resulting approaches. The kinematic constraint guaranteeing stress boundedness/continuity upon strain localization is established for general inelastic softening solids. Application to a unified elastoplastic damage model naturally yields all the ingredients of a localized model for the discontinuity (band), justifying the first methodology. Two dual but not necessarily equivalent approaches, i.e., the traction-based elastoplastic damage model and the stress-based projected discontinuity model, are identified. The former is equivalent to the embedded/smeared discontinuity approaches, whereas in the later the discontinuity orientation and associated failure criterion, not given a priori, are determined consistently from the kinematic constraint. The bi-directional connections and equivalence conditions between the traction- and stress-based approaches are classified. Closed-form 2D results under plane stress condition are also given, with the classical Rankine, Mohr-Coulomb, von Mises and Drucker-Prager criteria analyzed as the illustrative examples. A generic failure criterion of either elliptic, parabolic or hyperbolic type, is then considered in a unified manner, resulting in many failure criteria frequently employed in practice.