This paper considers the testability implications of low power design methodologies. Low power and high testability are shown to be highly contrasting requirements, and an optimization algorithm is proposed, which is able to explore the trade-off between them. The algorithm is based on a newly proposed power estimation function, and on an estimate of the expected test length of a pseudo-random test session. Given these estimates, a Genetic Algorithm, exploiting some symbolic computations with BDDs, provides a state re-encoding for the circuit. The algorithm is experimentally shown both to provide good results from the power optimization point of view, and to be able to sacrifice, on the designer's request, some of the power and area optimization in favor of testability improvement.