Yes, paint can be removed from brick with WD40. All you need is a sturdy scrub brush. Spray WD40 on the painted brick and start scrubbing.