We consider electroweak baryogenesis mediated by embedded domain walls. Embedded domain walls originating from a symmetry breaking phase transition are stabilized by thermal plasma effects, so that the electroweak symmetry is unbroken in their cores. For this reason, the cosmological evolution of such domain walls can generate a sufficiently large baryon asymmetry, irrespective of the order of the electroweak phase transition. For embedded domain walls, the condition that the energy of the universe not be dominated by the energy of the domain walls is relaxed significantly, and it is shown to be compatible with our scenario of electroweak baryogenesis.