The present study describes an in vitro characterization of strains of lactic acid bacteria, focusing on physiological characters of probiotic interest, and a subsequent placebo-controlled, crossover administration trial, with a cohort of healthy volunteers. The strains of lactic acid bacteria were previously isolated from a fermented food (ripened cheese) and several ones resulted to have promising probiotic characteristics. Based on comprehensive evaluation of the data obtained, one strain was chosen and supplemented in a fermented milk. The fermented milk was then used in the administration trial with the goal of assessing its effect on the composition of the intestinal microbiota, as reflected in the feces. The fermented milk, with or without probiotic, had an effect on the intestinal microbiota and significant inter-individual differences were observed in response to the intervention. A common trend was observed related to two important populations of the human gut microbiota; a reduction in the relative abundance of Bacteroides and increase in the abundance of Prevotella in subjects during treatment compared to baseline were registered.