Restoration of the electroweak symmetry at temperatures around the Higgs mass is linked to tight phenomenological constraints on many baryogenesis scenarios. A potential remedy can be found in mechanisms of electroweak symmetry non-restoration (SNR), in which symmetry breaking is extended to higher temperatures due to new states with couplings to the Standard Model. Here we show that, in the presence of a second Higgs doublet, SNR can be realized with only a handful of new fermions which can be identified as viable dark matter candidates consistent with all current observational constraints. The competing requirements on this class of models allow for SNR at temperatures up to $sim$TeV, and imply the presence of sub-TeV new physics with sizable interactions with the Standard Model. As a result this scenario is highly testable with signals in reach of next-generation collider and dark matter direct detection experiments.