After leaving Villanova in 2003, Sullivan travelled to the Netherlands to sign a professional contract with leading Dutch club EiffelTowers from the city of Nijmegen. After just one season in the Netherlands, Andrew returned to his homeland and immediately signed for leading British Basketball League team the Newcastle Eagles in 2004. Despite being pipped to the league title by just two points, "Sulli's" season was incredibly successful. Not only did he help his team win the Championship Play-offs in a 78–75 win over the Chester Jets, but he was also the game high scorer with 27 points and was named as the MVP of the Championship.