Mycobacterium avium subsp. paratuberculosis (MAP) is a pathogen causing paratuberculosis in cattle and small ruminants. During the long asymptomatic subclinical stage, high numbers of MAP are excreted and can be transmitted to food for human consumption, where they survive many of the standard techniques of food decontamination. Whether MAP is a human pathogen is currently under debate. The aim of this study was a better understanding of the host-pathogen response by analyzing the interaction of peripheral blood lymphocytes (PBL) from cattle with MAP in their exoproteomes/secretomes to gain more information about the pathogenic mechanisms of MAP. Because in other mycobacterial infections, the immune phenotype correlates with susceptibility, we additionally tested the interaction of MAP with recently detected cattle with a different immune capacity referred as immune deviant (ID) cows. In PBL, different biological pathways were enhanced in response to MAP dependent on the immune phenotype of the host. PBL of control cows activated members of cell activation and chemotaxis of leukocytes pathway as well as IL-12 mediated signaling. In contrast, in ID cows CNOT1 was detected as highly abundant protein, pointing to a different immune response, which could be favorable for MAP. Additionally, MAP exoproteomes differed in either GroEL1 or DnaK abundance, depending on the interacting host immune response. These finding point to an interdependent, tightly regulated response of the bovine immune system to MAP and vise versa.