We propose and discuss a novel strategy for protein design. The method is based on recent theoretical advancements which showed the importance to treat carefully the conformational free energy of designed sequences. In this work we show how computational cost can be kept to a minimum by encompassing negative design features, i.e., isolating a small number of structures that compete significantly with the target one for being occupied at low temperature. The method is successfully tested on minimalist protein models and using a variety of amino acid interaction potentials.