Nicholson was a late bloomer when it came to basketball; he did not start playing until his grade 11 season and due to a broken ankle missed the entire summer circuit prior to his senior season. For Nicholson baseball was his first passion but as he grew in size and athleticism he chose the game of basketball. Nicholson only gained recognition in his senior and 5th year. He was named to the Toronto Star High School All-Stars in 2007 and 2008 and also named MVP of five different tournaments.
On June 28, 2012, Nicholson was selected by the Orlando Magic with the 19th overall pick in the 2012 NBA Draft. In the month leading to the draft Nicholson travelled to 14 different cities, worked out for 12 different teams, and attended the NBA combine. On July 3, 2012, Nicholson signed his first professional contract with the Magic; the terms of the deal were undisclosed as per team policy. It was also confirmed that Nicholson and the Magic's second pick Kyle O'Quinn would participate on Orlando's summer league team. Nicholson in his first summer league game broke a tie with a spinning three-point play with 29.7 seconds remaining as the Magic defeated Brooklyn 92-88. He recorded a double-double against the Brooklyn Nets with 24 points and 12 rebounds, also adding 2 assists and 2 blocked shots. Nicholson made his regular season debut on November 2, 2012 against the Denver Nuggets, coming off the bench to record 2 points, 2 rebounds, 1 assist, and 1 block in 11 minutes. He made his first career start on December 21, 2012 against the Toronto Raptors in place of an injured Glen Davis. He finished with 6 points, 4 rebounds, 1 assist and 1 blocked shot in 20 minutes. He scored a game and career high 22 points in his second career start, also against the Raptors, on December 29, 2012, and also grabbed 7 rebounds and 1 steal in 26 minutes. Andrew recorded his first double-double of his career in a start against the Boston Celtics, scoring 14 points and grabbing a career high 10 rebounds, 1 assist, 1 steal, and 2 blocked shots in 33 minutes. On February 10, 2013 Andrew Nicholson was selected to replace the injured Andre Drummond in the Rising Stars Challenge during the 2013 NBA All-Star Weekend on February 17, 2013 in Houston, Texas.