Infection with Mycobacterium avium subspecies paratuberculosis (MAP) is complex, but little is known about the role that natural killer (NK) cells play. In the present study, four bovine NK-lysin peptides were synthesized to evaluate their bactericidal activity against MAP. The results demonstrated that bNK-lysin peptides were directly bactericidal against MAP, with bNK1 and bNK2A being more potent than bNK2B and bNK2C. Mechanistically, transmission electron microscopy revealed that the incubation of MAP with bNK2A resulted in extensive damage to cell membranes and cytosolic content leakage. Furthermore, the addition of bNK2A linked with a cell-penetrating peptide resulted in increased MAP killing in a macrophage model.