The quality of concrete of the most of Algerian construction sites is often low. In the case of low compressive strength results, non-destructive tests such as rebound hammer and ultrasonic pulse velocity are performed to check these results. Correlations curves from either equipment manufacturers or from the literature are used by quality control laboratories in order to estimate concrete strength. The estimation of strength based on these correlations is often subject to confusion and contradictory results when compared with the core test results. This clearly shows the need for appropriate correlations for concrete made with local materials and under local environmental conditions. The main objective of this paper is to propose appropriate simplified correlations for concretes made by local materials and for compressive strength levels reflecting the conditions and current practices on building sites in Algeria. This study presents some models established between destructive and individual or combined nondestructive tests (Rebound hammer and ultrasonic pulse velocity) in order to obtain a better estimation of concrete strength on site. The results show the reliability of the combined methods and the important difference in concrete strength estimation as compared to the models available in the literature.