Paratuberculosis is a worldwide disease mainly introduced through trade. Due to the low sensitivity of diagnostic tests, it is difficult to protect herds from purchasing infected animals. Our objective was to assess if rewiring trade networks to promote risk-based movements could reduce the spread of Mycobacterium avium subsp. paratuberculosis (MAP) between dairy cattle herds at a regional scale. Two levels of control strategies were assessed. At the between-herd scale, trade rewiring aimed to prevent animals from high-risk herds moving into low-risk herds. At the within-herd scale, complementary additional measures were considered based on the herd infection status, aiming to limit the within-herd spread by reducing calf exposure to adult faeces and culling more rapidly after positive test results. We used a stochastic individual-based and between-herd mechanistic epidemiological model adapted to the 12,857 dairy cattle herds located in Brittany, western France. We compared the regional spread of MAP using observed trade movements against a rewiring algorithm rendering trade movements risk-based. All females over two years old were tested. Based on the results, and taking into account the low test sensitivity, herds were annually assigned one of three statuses: A if the estimated true prevalence was below 7%, B if it ranged from 7 to 21 %, C otherwise. We also identified herds with a high probability of being MAP-free (AAA herds that had obtained an A status over three consecutive years) to assess the effect of decreasing their risk of purchasing infected animals on MAP regional spread. We showed that movement rewiring to prevent the sale of animals from high to low-prevalence herds reduces MAP regional spread. Targeting AAA herds made it possible to minimize the control effort to decrease MAP regional spread. However, animals purchased by AAA herds should have a moderate to high probability of being MAP-free, especially if the risk of purchasing animals from herds of unknown status cannot be managed. Improved hygiene and early culling of positive animals were relevant complementary on-farm control options to further decrease MAP spread. Future studies should identify how to define herd statuses to target optimal control measure combinations that could reduce the spread of MAP on a regional scale most effectively.