Yes, olives are Paleo. Though they are often processed to make them edible, they still are paleo-friendly.