Single-cell protein (SCP) from agro-waste material has gained increased attention in the recent past as a relatively cheap and alternative protein source to meet the nutritional demand generated by the fast-growing population. Furthermore, bioconversion of these wastes into SCP such as value-added products reduce the environmental-related issues. In this study, locally available pineapple (Ananas comosus), watermelon (Citrullus lanatus), papaya (Carica papaya), sour orange (Citrus medica), banana (Musa acuminata) and mango (Mangifera indica) peel wastes were investigated for their suitability to produce SCP using palmyrah (Borassus flabellifer) toddy carrying natural mixed yeast and bacteria culture under liquid state fermentation system. Moreover, this study attempted to select the best substrate and the optimized process condition for SCP production to increase the protein yield. The physicochemical properties of selected fruit peels were analyzed. The sterilized peel extracts (10%, v/v) were inoculated with 5 mL of palmyrah toddy and allowed to ferment in a shaking incubator at 100 rpm for 48 h in triplicate At the end of fermentation, the sediments were collected by centrifugation at 1252× g, oven-dried, and the dry weight was taken to determine the protein content. The biomass yield ranged from 5.3 ± 0.6 to 11.7 ± 0.8 g/L, with the least biomass yield being observed with watermelon peels while the maximum yield was observed with papaya peels. Papaya peel generated a significantly higher (p < 0.05) amount of protein (52.4 ± 0.4%) followed by pineapple (49.7 ± 1.3%), watermelon (45.2 ± 0.7%), banana (30.4 ± 0.6%), sour orange (29.5 ± 1.2%) and mango (24.6 ± 0.2%) peels. The optimum condition for the fermentation of papaya waste was pH 5.0, 25 °C, and 24 h. Nucleic acid reduction treatment significantly reduces dry weight and protein content of biomass. It can be concluded that papaya peel waste is a suitable substrate for protein-rich cell biomass production using the natural toddy mixed culture of palmyrah.