The state of stone historical monuments in Algeria is outlined: prehistoric paintings at Tassili (Sahara), engravings at Djelfa and some of the numerous Roman sites at Timgad, Djemila, and Tigzirt. The problems of conservation and the evaluation of stone structures are thoroughly examined, including a comparison of ultrasonic and sclerometric methods for structural analysis and the detection of cement repairs. Proposals of successive improvement of the actual state of conservation as well as the introduction of some modern nondestructive methods are given.