Background Shifting towards a more plant-based diet, as promoted in Western countries, will reduce the animal protein contribution to total proteins. Such a reduction may not only impair protein adequacy, but also the adequacy in other nutrients. Objectives We determined, for different adult subpopulations, the minimum total protein level and the minimum animal protein contribution to total proteins that are compatible with the fulfillment of all non-protein nutrient-based recommendations. Methods Mean nutritional content and mean diet cost for 5 French subpopulations were estimated using a French cross-sectional representative survey: Women < 50 years (A), Women 50–64 years (B), Women ≥ 65 years (C), Men < 65 years (D), Men ≥ 65 years (E). For each subpopulation, linear programming optimization was used to assess the minimum protein level (Model Set#1) and the minimum animal protein contribution to total proteins (Model Set#2) that are compatible with the fulfilment of all nutrient-based recommendations (except proteins for which levels were analyzed as output). Total diet cost was not allowed to increase. Eating habits were considered in Model Set#2 only. Results The minimum amount of protein that was theoretically compatible with the fulfilment of nutrient-based recommendations (Model Set#1) was below the minimum recommended protein intake for all subpopulations except A. In Model Set#2, for women and men over 65 years (C and E), decreasing animal protein contribution to total proteins below 55% and 60% respectively led to protein levels below recommend levels. For the other subpopulations (A, B, and D), the lowest animal protein contribution to total proteins compatible with a nutritionally adequate diet (including protein adequacy) was 55%, 50% and 45%, respectively. Conclusion This study provides factual information about the animal protein contribution to total proteins compatible with meeting all nutrient-based recommendations at no additional cost and shows that it varies between 45% and 60% depending on the group of adults considered.