For best results, yes. Thermal paste should be re-applied each time the cooler is removed. Otherwise, air bubbles can form and reduce cooling capability.
The AiO typically will have pre-applied thermal paste. So the old paste should be removed anyway. For custom builders, it's always good to have extra thermal paste available to you.