Την απόκτηση του Ανδρέα Χριστοδούλου που την περασμένη σεζόν αγωνίστηκε στον Κόροιβο ανακοίνωσε η ΚΑΕ Ρέθυμνο Cretan Kings. Ο 21χρονος διεθνής γκαρντ-φόργουορντ συμφώνησε με την κρητική ομάδα για συμβόλαιο δύο χρόνων.

Η ανακοίνωση με το βιογραφικό του: «Η ΚΑΕ Ρέθυμνο Cretan Kings ανακοινώνει την έναρξη της συνεργασίας με τον καλαθοσφαιριστή Ανδρέα Χριστοδούλου για δύο χρόνια. Ο Ανδρέας Χριστοδούλου γεννήθηκε στις 22 Φεβρουαρίου 1995 στην Κύπρο, έχει ύψος 1.97 και αγωνίζεται ως σούτινγκ γκαρντ ή σμολ φόργουορντ.

Η επαγγελματική σταδιοδρομία του Ανδρέα Χριστοδούλου ως καλαθοσφαιριστής ξεκίνησε στην ΑΕΛ Λεμεσού, στην οποία αγωνίστηκε μέχρι το καλοκαίρι του 2011. Επόμενος σταθμός της καριέρας του ήταν ο ΑΠΟΕΛ, στην οποία αγωνίστηκε για μία σεζόν.
Το καλοκαίρι του 2012, μεταπήδησε από την Κύπρο στην Ελλάδα για λογαριασμό του ΜΑΣ Μαντουλίδη, όπου παρέμεινε για μία σεζόν.

Το 2013, τον απέκτησε ο Ολυμπιακός, υπογράφοντας με τους «ερυθρόλευκους» συμβόλαιο πενταετούς διαρκείας. Ο Χριστοδούλου κατέκτησε λίγους μήνες μετά τη μεταγραφή του στους ερυθρόλευκους τον πρώτο του τίτλο, ο οποίος μάλιστα ήταν και διεθνής. Ο λόγος για το Διηπειρωτικό Κύπελλο, το οποίο κατέκτησε ο Ολυμπιακός μετά από δύο νίκες σε ισάριθμους αγώνες με αντίπαλο την Πινιέιρος. Την επόμενη χρονιά πανηγύρισε την κατάκτηση του ελληνικού πρωταθλήματος.

Πέρυσι παραχωρήθηκε ως δανεικός στον Κόροιβο και σε 22 παιχνίδια και 12.57 λεπτά συμμετοχής, είχε 3.95 πόντους (69.23% βολές, 42.86% δίποντα, 20.83% τρίποντα), 1.59 ριμπάουντ, 0.64 ασίστ και 0.27 κλεψίματα κατά μέσο όρο.

Το 2014, μετά και την απόκτηση της ελληνικής υπηκοότητας, ο Χριστοδούλου ήταν μέλος της εθνικής ομάδας Κ20, με την οποία συμμετείχε στο αντίστοιχο πανευρωπαϊκό πρωτάθλημα την ίδια χρονιά».