Related to previous reports on correlations between an animal’s genotype, its commensal microbiota, and the ability to resist infections, the aim of the current study was to investigate the associations between sheep genotype and 5-methylcytosine (5-mC) DNA methylation patterns, sheep genotype and cell surface hydrophobicity of sheep gut commensal bacteria. In addition, the effect of the probiotic Lactobacillus acidophilus strain INMIA 9602 Er 317/402 (probiotic formulation Narine) on Salmonella carriage in sheep at Armenian farms was also investigated. Allelotypes and genotypes of different pathogen-sensitive sheep breeds from Armenian farms were studied based on genetic markers of blood transferrin, albumin, and ceruloplasmin. Additionally, the differences between the breeds of Mazekh, Balbas, and Mazekh/Balbas hybrids were reported. The relationship between host sheep blood transferrin and albumin polymorphisms and cell surface hydrophobicity/5-mC DNA methylation patterns from the predominant gut commensal bacteria was shown. The Narine probiotic eliminates Salmonella from the sheep gut microbiota. At the same time, no significant changes in the percentage of 5-mC DNA methylation of predominant gut bacteria after probiotic administration were observed. The evaluation of bacterial cell surface hydrophobicity, the most significant factor affecting bacterial adhesion, as well as 5-mC DNA methylation, might be used for specific sheep husbandry/breeding programs. This study suggests that the commercial probiotic Narine could potentially be used to reduce Salmonella carriage in sheep.