The utilization of coal bottom ash (CBA) as natural sand replacement in mortar is a feasible solution to reduce the environmental issues created due to its disposal. However, strength behavior of CBA mortar varies from conventional natural sand mortar. For design and quality control in the field, there is a need to assess the feasibility of nondestructive test methods in estimating the in situ mechanical properties of CBA mortar. To address this, the present research study elaborates the correlation between compressive strength and ultrasonic pulse velocity to predict the compressive strength of CBA mortar using UPV test. The influence of CBA replacement level and curing age was examined. The experimental program involves two mortar mix proportioned cement-fine aggregate ratios of 1:3 and 1:5 having standard flow of 110–115%. The natural sand replacement with CBA varies from 20 to 100% in increment of 20%. Control mortar mix contains 100% natural sand. Mortar samples were casted, cured at ambient temperature and then tested at curing age of 7 days, 28 days, 56 days, 90 days and 120 days. Workability and density test of mortar specimens have also conducted for reference. Results indicate that the UPV and compressive strength of CBA mortar were lower than those of the control mortar for all replacement levels at all curing age and for all mixes. The empirical relationships obtained between compressive strength and UPV were exponential in nature with high correlation coefficient varying from 0.91 to 0.99. The feasibility of developed empirical equations in predicting the compressive strength was validated by comparing the predicted results with measured test results. © 2021, The Institution of Engineers (India).