Belgium obtained the bovine tuberculosis (bTB) officially free status in 2003 (EC Decision 2003/467/EC). This study was carried out to evaluate the components of the current bTB surveillance program in Belgium and to determine the sensitivity of this program. Secondly, alternatives to optimize the bTB surveillance in accordance with European legislation (Council Directive 64/432/EEC) were evaluated. Separate scenario trees were designed for each active surveillance component of the bTB surveillance program. Data from 2005 to 2009 regarding cattle population, movement and surveillance were collected to feed the stochastic scenario tree simulation model. A total of 7,403,826 cattle movement history records were obtained for the 2,678,020 cattle from 36,059 cattle herds still active in 2009. The current surveillance program sensitivity as well as the impact of alternative surveillance protocols was simulated in a stochastic model using 10,000 iterations per simulation. The median (50% percentile) of the component sensitivities across 10,000 iterations was 0.83, 0.85, 0.99, 0.99, respectively, for (i) testing the cattle only during the winter screening, (ii) testing only imported cattle, (iii) testing only purchased cattle and (iv) testing only all slaughtered cattle. The sensitivity analysis showed that the most influential input parameter explaining the variability around the output came from the uncertainty distribution around the sensitivity of the diagnostic tests used within the bTB surveillance. Providing all animals are inspected and post mortem inspection is highly sensitive, slaughterhouse surveillance was the most effective surveillance component. If these conditions were not met, the uncertainty around the mean sensitivity of this component was important. Using an antibody ELISA at purchase and an interferon gamma test during winter screening and at import would increase greatly the sensitivity and the confidence level of Belgium's freedom from bTB infection status.