The development of sustainable lightweight materials is a promising field solution in this era. The production of sustainable materials by replacing coarse aggregates with some lightweight alternative provides a good quality construction material. In this study, rocky coarse aggregates were replaced by an ultra-lightweight material (i.e., expanded polystyrene beads) to produce an equivalent rock-solid mass of concrete. Using an M15 grade of concrete composition, expanded polystyrene (EPS) beads were added in place of aggregates in amounts ranging from 5% to 40% at a water−cement (w/c) ratio of 0.60. The specimen size as per American Society for Testing and Materials (ASTM) specification was 150 mm in diameter and 300 mm in length. Furthermore, statistical analysis for the relationship study for destructive testing (DT) (i.e., compressive test machine) and non-destructive testing (NDT) (i.e., rebound hammer and ultrasonic pulse velocity (UPV)) has been performed at developed specimens under 7- and 28-day curing conditions. In the end, the results showed that NDT predicts higher compressive strength than that of DT with the addition of EPS beads up to 20% aggregate replacement, after that it is vice versa for up to 40% aggregate replacement. This study will not only help in the production of sustainable lightweight materials, but especially concrete block production can also be performed at a large scale as a sustainable engineering solution.