Bovine paratuberculosis is mainly spread between herds due to trade movements of infected and undetected animals. The prevalence worldwide being high at animal and herd levels, and infected animals being hard to detect using routine diagnostic tests, the disease spread cannot be easily observed in the field, whereas there is a need for assessing control strategies. Our objective is to better understand the spread of Mycobacterium avium subsp. paratuberculosis (Map) at a regional scale using a modelling approach, and to compare through intensive simulations complex control strategies combining biosecurity measures (early culling, hygiene improvement, calf management) and tests-at-purchase. We developed the first multi-scale mechanistic model of Map spread between dairy cattle herds, accounting for stochastic within-herd dynamics (demography and infection), indirect local transmission, and incorporating data on animal trade and on herd-specific size and management. We modeled all of the 12,857 dairy herds located in Brittany (France) having more than 15 dairy females. Data from 2005 to 2013 was used to calibrate each herd size and demographic rates, and to define trade events. We assumed initially 30% of the herds to be infected with a 10% within-herd prevalence on average. Each measure tested alone or in combination with tests at purchase succeeded in slowing down the regional Map spread, but not in decreasing the proportion of infected herds. More than two measures had to be combined to effectively reduce the herd-level prevalence. In such a case, only a moderate level of implementation of each measure was required, indicating the operational potential of such combined strategies. Our study highlights the challenge of controlling Map spread in an endemically infected region because of poor test characteristics and frequent trade movements. Our model is a flexible and efficient tool to help collective animal health managers in defining relevant control strategies at a regional scale, accounting for regional specificities in terms of contact network and farm characteristics