A new technique, node sampling, is proposed, to speed up probability-based power estimation methods. This technique samples and processes only a small portion of the total nodes to estimate the power consumption of a circuit. It is different from previous speed-up techniques for probability-based methods which reduce the processing time for each node, and is also different from the sampling techniques for simulation-based methods which sample input vector sequences. The experimental results demonstrate the validity of the proposed method.