Paratuberculosis is a major disease in cattle that severely affects animal welfare and causes huge economic losses worldwide. Development of alternative diagnostic methods is of urgent need to control the disease. Recent studies suggest that long non-coding RNAs (lncRNAs) play a crucial role in regulating immune function and may confer valuable information about the disease. However, their role has not yet been investigated in cattle with respect to infection towards Paratuberculosis. Therefore, we investigated the alteration in genomic expression profiles of mRNA and lncRNA in bovine macrophages in response to Paratuberculosis infection using RNA-Seq. We identified 397 potentially novel lncRNA candidates in macrophages of which 38 were differentially regulated by the infection. A total of 820 coding genes were also significantly altered by the infection. Co-expression analysis of lncRNAs and their neighbouring coding genes suggest regulatory functions of lncRNAs in pathways related to immune response. For example, this included protein coding genes such as TNIP3, TNFAIP3 and NF-κB2 that play a role in NF-κB2 signalling, a pathway associated with immune response. This study advances our understanding of lncRNA roles during Paratuberculosis infection.