The development of new types of environmentally friendly and cost-effective building materials is currently a relevant topic and is actively developing throughout the world. In modern construction materials science, the most popular direction is the development of new concrete compositions using waste of various origins. The objective of this study is to develop new compositions of foam concrete using local waste from the fuel and energy complex and plant natural fibers. To determine the optimal amount of the modifying additive fly ash (FA), 7 experimental concrete compositions with different percentages of cement replacement by FA were made. The content was established as optimal. Foam concrete with 15% FA has the lowest density of 1075 kg/m3 and a minimum thermal conductivity coefficient of 0.248 W/m × °C, as well as increases in compressive and bending strength of 23.3% and 21.7%, respectively. The effect of coconut fiber (CF) was assessed on the composition of foam concrete modified with the optimal amount of FA 15%. The optimal dosage of CF was 0.6%. As a result of FA modification and CF dispersed reinforcement, a complex effect was obtained. The increase in compressive and bending strength was 30.14% and 72.83%, respectively, compared to conventional foam concrete. The density and thermal conductivity coefficient decreased by 9.8% and 8.34%, respectively. The results obtained during the experimental studies prove the effectiveness of the proposed formulation solutions and allow obtaining an energy-efficient foam concrete composite with improved characteristics.