In this paper, we study “complete instability” of interval polynomials, which is the counterpart of classical robust stability. That is, the objective is to check if all polynomials in the family are unstable. If not, a subsequent goal is to find a stable polynomial. To this end, we first propose a randomized algorithm which is based on a (recursive) necessary condition for Hurwitz stability. The second contribution of this paper is to provide a probability-one estimate of the volume of stable polynomials. These results are based on a combination of deterministic and randomized methods. Finally, we present two numerical examples and simulations showing the efficiency of the proposed methodology for small and medium-size problems.