Conventional scenarios of electroweak (EW) baryogenesis are strongly constrained by experimental searches for CP violation beyond the SM. We propose an alternative scenario where the EW phase transition and baryogenesis occur at temperatures of the order of a new physics threshold far above the Fermi scale, say, in the 100-1000 TeV range. This way the needed new sources of CP-violation, together with possible associated flavor-violating effects, decouple from low energy observables. The key ingredient is a new CP- and flavor-conserving sector at the Fermi scale that ensures the EW symmetry remains broken and sphalerons suppressed at all temperatures below .We analyze a minimal incarnation based on a linear O(N) model. We identify a specific large-N limit where the effects of the new sector are vanishingly small at zero temperature while being significant at finite temperature. This crucially helps the construction of realistic models. A number of accidental factors, ultimately related to the size of the relevant SM couplings, force N to be above approximate to 100. Such a large N may seem bizarre, but it does not affect the simplicity of the model and in fact it allows us to carry out a consistent re-summation of the leading contributions to the thermal effective potential. Extensions of the SM Higgs sector can be compatible with smaller values N approximate to 20-30.Collider signatures are all parametrically suppressed by inverse powers of N and may be challenging to probe, but present constraints from direct dark matter searches cannot be accommodated in the minimal model. We discuss various extensions that satisfy all current bounds. One of these involves a new gauge force confining at scales between approximate to 1 GeV and the weak scale.