Σε απόσταση 5-6 χλμ. Β-Δυτικά της Ν. Καλλικράτειας βρίσκεται ο οικισμός της Νέας Ηράκλειας, που ανήκει στο Δημοτικό Διαμέρισμα (Δ. Δ.) Αγίου Παύλου.
Έχει 698 κατοίκους που ασχολούνται κυρίως με τον τουρισμό, τη γεωργία (αμπελουργία) και το ψάρεμα. Με ήπιες κλίσεις, το έδαφος κατεβαίνει ομαλά προς την ακτή με ταπεντακάθαρα νερά, τις όμορφες και ήσυχες παραλίες και τις γραφικές ψαροταβέρνες, τις σχεδόν «πάνω στο κύμα», όπου, κάτω από παχύσκια πεύκα μπορεί ο επισκέπτης να γευτεί γαρίδα σαχανάκι και πολλές άλλες θαλασσινές και όχι μόνον λιχουδιές.Εδώ βρέθηκε αργυρή λειψανοθήκη του 4ου και 5ου μ.Χ. αιώνα, με γλυπτές παραστάσεις από την Παλαιά και την Καινή Διαθήκη και στις τέσσερις πλευρές της. Οι κάτοικοι έχουν οργανωμένο τοπικό Ποδοσφαιρικό Σύλλογο και Πολιτιστικό και στις 23 Απριλίου κάθε χρόνο, τιμούν την γιορτή της εκκλησίας του χωριού, του Αϊ-Γιώργη.