In this paper, we present a progressive classification scheme for a document layout recognition system using three stages. The first stages, preprocessing, extracts statistical information that may be used for background detection and removal. The second stage, a tree based classified, uses a variable block size and a set of probabilistic rules to classify segmented blocks that are independently classified. The third, state, postprocessing, uses the label map generated in the second state with a set of context rules to label unclassified blocks, trying also to solve some of the misclassification errors that may have been generated during the previous stage. The progressive scheme used in the second and third stages allows the user to stop the classification process at any block size, depending on this requirements. Experiments show that a progressive scheme combined with a set of postprocessing rules increases the percentage of correctly classified blocks and reduces the number of block computations.