The high stiffness of cement-bound aggregate (CBA) is recognized as its main drawback. The stiffness is described by the modulus of elasticity, which is difficult to determine precisely in CBA. Incorporating rubber in these mixtures reduces their stiffness, but mathematical models of the influence of rubber on the mechanical characteristics have not previously been defined. The scope of this research was to define a prediction model for the compressive strength (fc), dynamic modulus of elasticity (Edyn) and static modulus of elasticity (Est) based on the measured ultrasonic pulse velocity as a non-destructive test method. The difference between these two modules is based on the measurement method. Within this research, the cement and waste rubber content were varied, and the mechanical properties were determined for three curing periods. The Edyn was measured using the ultrasonic pulse velocity (UPV), while the Est was determined using three-dimensional digital image correlation (3D DIC). The influence of the amount of cement and rubber and the curing period on the UPV was determined. The development of prediction models for estimating the fc and Est of CBA modified with waste rubber based on the non-destructive test results is highlighted as the most significant contribution of this work. The curing period was statistically significant for the prediction of the Est, which points to the development of CBA elastic properties through different stages during the cement-hydration process. By contrast, the curing period was not statistically significant when estimating the fc, resulting in a simplified, practical and usable prediction model.