This study was developed to investigate the potential re-utilization of waste incineration bottom ash (IBA) sourced from Southern Vietnam as a replacement for natural crushed sand in cement based mortars. In this study, all of the mortar mixtures were designed using the novel densified mixture design algorithm with a detailed step-by-step standard operating procedure and an empirical example of the calculation. Changes in the engineering properties (i.e., flowability, fresh unit weight, compressive strength, bending strength, and drying shrinkage), durability (i.e., porosity, water absorption, chloride ion penetration, ultrasonic pulse velocity, and resistance to sulfate attack), and microstructure of the mortars were systematically evaluated using mortar specimens produced with five different IBA replacement levels of 0, 25, 50, 75, and 100% (by volume). Moreover, the correlations among these several mortar properties were established and discussed. The experimental results indicate that the IBA replacement level significantly affects the properties of mortars in both fresh and hardened stages. Increasing the IBA replacement level was found to increase porosity, water absorption, and drying shrinkage and to reduce compressive and bending strengths in the mortar specimens. Moreover, increasing the IBA replacement level reduced resistance to sulfate attack. However, all of the proposed mortars exhibited very good chloride penetration resistance and good quality, with chloride ion penetration and ultrasonic pulse velocity values ranging from 355 to 638 Coulombs and 3483–4416 m/s, respectively, at 56 days of curing age.