The problem of tagging words with their parts-of-speech has received considerable attention in the last few years and several methods for solving it have been developed. Word labeling is usually accomplished by predicting, for each word, the list of its possible labels, and then making a selection on the basis of context. In this paper the use of probabilistic decision trees for part-of-speech prediction is proposed. The tree is automatically constructed using a recent partitioning algorithm that works in linear time, and then pruned with a generalized "reduced-error" algorithm. Preliminary experiments conducted over the LOB Corpus are presented.