Surveillance of infectious diseases in livestock is traditionally carried out at the farms, which are the typical units of epidemiological investigations and interventions. In Central and Western Europe, high-quality, long-term time series of animal transports have become available and this opens the possibility to new approaches like sentinel surveillance. By comparing a sentinel surveillance scheme based on markets to one based on farms, the primary aim of this paper is to identify the smallest set of sentinel holdings that would reliably and timely detect emergent disease outbreaks in Swiss cattle. Using a data-driven approach, we simulate the spread of infectious diseases according to the reported or available daily cattle transport data in Switzerland over a four year period. Investigating the efficiency of surveillance at either market or farm level, we find that the most efficient early warning surveillance system [the smallest set of sentinels that timely and reliably detect outbreaks (small outbreaks at detection, short detection delays)] would be based on the former, rather than the latter. We show that a detection probability of 86% can be achieved by monitoring all 137 markets in the network. Additional 250 farm sentinels—selected according to their risk—need to be placed under surveillance so that the probability of first hitting one of these farm sentinels is at least as high as the probability of first hitting a market. Combining all markets and 1000 farms with highest risk of infection, these two levels together will lead to a detection probability of 99%. We conclude that the design of animal surveillance systems greatly benefits from the use of the existing abundant and detailed animal transport data especially in the case of highly dynamic cattle transport networks. Sentinel surveillance approaches can be tailored to complement existing farm risk-based and syndromic surveillance approaches.