It depends on the kind of paint you use. Our sponges didn't stain (they were also washed quickly after the project was done).