Currently, the majority of prebiotics in the market are derived from non-digestible oligosaccharides. Very few studies have focused on non-digestible long chain complex polysaccharides in relation to their potential as novel prebiotics. Cereals β-glucans have been investigated for immune-modulating properties and beneficial effects on obesity, cardiovascular diseases, diabetes, and cholesterol levels. Moreover, β-glucans have been reported to be highly fermentable by the intestinal microbiota in the caecum and colon, and can enhance both growth rate and lactic acid production of microbes isolated from the human intestine. In this work, we report the effects of food matrices containing barley β-glucans on growth and probiotic features of four Lactobacillus strains. Such matrices were able to improve the growth rate of the tested bacteria both in unstressed conditions and, importantly, after exposure to in vitro simulation of the digestive tract. Moreover, the effect of β-glucans-containing food on bacterial adhesion to enterocyte-like cells was analyzed and a positive influence on probiotic-enterocyte interaction was observed.