This paper presents a machine learning (ML) model for predicting concrete strength using a combination of two non-destructive testing (NDT) methods: ultrasonic pulse velocity (UPV) and rebound number (RN). The model was developed using an extensive and diverse dataset and is the first such model to consider the effect of three different sample types: cubic, cylindrical, and core samples. This study is also the first of its kind to present an in-depth analysis of the results to quantify model uncertainty, which is an important prerequisite for its use in practice. Accordingly, two ML models were trained using 620 data points from the aforementioned sample types. The prediction intervals and associated uncertainties of the ML-based approach were thoroughly examined. Validation with the testing dataset showed that 93% of the testing data points for the combined cylindrical and cubic dataset fell within the 95% prediction interval, indicating strong alignment with expected results. Based on the findings, a roadmap is also proposed for future work.