Lentils (Lens culinaris) present an excellent nutrient profile. However, the increasing displacement of legumes from the diet and the possible negative effects of the food matrix and antinutrient factors encourage the application of new strategies to improve nutrient digestibility and to produce food concepts that contribute to the increase of legume consumption. This study approached the solid-state fermentation of lentils with an edible fungus (Pleurotus ostreatus) in order to produce improved lentil flour. Fermentation contributed to the increase of protein (23%), resistant starch (9.8%), and polyphenols (from 2.1 to 3.2 mg gallic acid equivalent per g dry matter). After simulating in vitro digestion, fermented flours presented a higher fraction of digested protein (17%) along with lower starch hydrolysis (34 vs. 24%), while the polyphenol content increased from 3.1 to 7.73 mg gallic acid equivalent per g dry matter. Thus, this study supports the application of solid-state fermentation with this edible fungus to obtain lentil flours with an enhanced digestibility profile as compared to non-fermented counterparts. Lentil flours could be used as a novel raw material in the formulation of new food concepts with an enhanced nutritional profile.