Meat represents an important protein source, even in developing countries, but its production is scarcely sustainable, and its excessive consumption poses health issues. An increasing number of Western consumers would replace, at least partially, meat with alternative protein sources. This review aims at: (i) depicting nutritional, functional, sensory traits, and critical issues of single-cell proteins (SCP), filamentous fungi, microalgae, vegetables (alone or mixed with milk), and insects and (ii) displaying how fermentation could improve their quality, to facilitate their use as food items/ingredients/supplements. Production of SCP (yeasts, filamentous fungi, microalgae) does not need arable land and potable water and can run continuously, also using wastes and byproducts. Some filamentous fungi are also consumed as edible mushrooms, and others are involved in the fermentation of traditional vegetable-based foods. Cereals, pseudocereals, and legumes may be combined to offer an almost complete amino acid profile. Fermentation of such vegetables, even in combination with milk-based products (e.g., tarhana), could increase nutrient concentrations, including essential amino acids, and improve sensory traits. Different insects could be used, as such or, to increase their acceptability, as ingredient of foods (e.g., pasta). However, insects as a protein source face with safety concerns, cultural constraints, and a lack of international regulatory framework.