We present a method for incremental evaluation of a Belief Network (BN). Evaluation is initially performed on a restricted number of nodes in the immediate vicinity of the query nodes. The BN is then traversed radially out from each query node and estimates for the belief of the query node are computed iteratively. This incremental evaluation results in a form of anytime algorithm. A best-first graph traversal strategy requires an assessment of the relative importance of various nodes in terms of contributing the most towards a query node. At each step, we must visit in priority the most significant nodes while making a trade-off with computation cost. We use the concept of arc weights in a BN to determine to what extent a node influences the query node. We also incorporate a measure of the computation cost of visiting a node, in terms of the state space sizes of the node and of its parents.