An on-line structure-learning algorithm of belief network is proposed. The basic idea is to incrementally update the structure and parameters of a belief network after each group of data samples is received. The algorithm consists of two steps. The first step is to update the current belief network based on newly received data samples using incremental updating rules, including parameter incremental updating rule and three structure incremental updating rules, which are adding edge, deleting edge and reverting edge. The second step is to use the result selection criterion to select the most appropriate result from the set of candidates resulted by the first step. The selection criterion fulfills the desire to balance the consistency of the result with the newly received data against the distance between the result and the previous model. Experimental results show that the algorithm can efficiently perform on-line learning of belief network structure. Since on-line learning does not need history data and can adapt to the variation of the problem domain, this algorthm is suitable to model those domains that vary with time.