Παρότι λείπει για χρόνια από την Ελλάδα, ο Απόστολος Βέλλιος έχει χτίσει τη δική του παράδοση απέναντι στους «ασσπρόμαυρους». Είναι άλλωστε ένας σέντερ φορ που έχει δείξει ότι δεν «κολλάει» απέναντι σε μεγάλους αντιπάλους.

Ο διεθνής επιθετικός αντιμετώπισε πρώτη φορά τον ΠΑΟΚ το 2010 με τη φανέλα του Ηρακλή, όπου όμως αγωνίστηκε 4' στο ματς του Καυτανζογλείου και 6' σε αυτό της Τούμπας, όντας ακόμα πιτσιρικάς. Στη συνέχεια, έφυγε στο εξωτερικό για την Έβερτον και έκανε ένα διάλειμμα επιστροφής στην Ελλάδα το 2015, όπου φόρεσε ξανά τη φανέλα του Ηρακλή και βρήκε τον καλό του εαυτό! Αυτή τη φορά, έπαιξε 90' απέναντι στον δικέφαλο του βορρά στο εντός έδρας ματς της ομάδας του και άνοιξε λογαριασμό!

Το ματς μάλιστα ήταν θρίλερ, αφού έληξε 3-3, με τον Μπαρτολίνι να ισοφαρίζει για τον Γηραιό στο 90'! Ο Βέλλιος είχε σημειώσει το δεύτερο γκολ της ομάδας του στο 43'. Στη ρεβάνς της Τούμπας, ο Ηρακλής είχε πάρει σπουδαία νίκη με γκολ του Λεοζίνιο στο 72' και ο υψηλόσωμος φορ ήταν εκείνος που του είχε δώσει την ασίστ.

Ο Βέλλιος ξενιτεύτηκε ξανά στη συνέχεια, για λογαριασμό της Νότιγχαμ Φόρεστ. Φέτος επέστρεψε και πάλι στην Ελλάδα για λογαριασμό του Ατρόμητου και «πλήγωσε» τον ΠΑΟΚ με δύο γκολ στο Περιστέρι, τα οποία όμως δεν ήταν αρκετά για να πάρει η ομάδα του τη νίκη.