Previous algoritms for the construction of belief networks structures from data are mainly based either on independence criteria or on scoring metrics. The aim of this paper is to present a hybrid methodology that is a combination of these two approaches, which benefits from characteristics of each one, and to introduce an operative algoritm based on this methodology. We dedicate a special attention to the problem of getting the ‘right’ size of the belief network induced from data, i.e. finding a trade-off between network complexity and accuracy. We propose several approaches to tackle this matter. Results of the evaluation of the algorithm on the well-known Alarm network are also presented.