We propose a new technique called node sampling to speed up the probability-based power estimation methods. It samples and processes only a small portion of total nodes to estimate the power consumption of a circuit. It is different from the previous speed-up techniques for probability-based methods in that the previous techniques reduce the processing time for each node while our method reduces the number of nodes actually processed. In addition, it is also different from the previous statistical sampling simulation techniques for simulation-based methods in that the previous methods sample the input vectors while our method samples the nodes in the network. The experimental results are very encouraging. The proposed method shows on the average more than 80% and 60% reductions of simulation run time under 20% and 5% error bounds, respectively.