This also varies, as different stones may be more or less durable than others. The paint on a stone may also fade over time if it's exposed to harsh elements. However, as long as the stone is left undisturbed, the paint should last for quite some time.