Phillips was drafted by the Milwaukee Brewers as a shortstop in the 41st round of the 1995 draft as a high school senior and again by the New York Yankees in the 7th round of the 1999 draft as a college graduate of the University of Alabama. He signed with the Yankees, but did not reach the Major Leagues until a call-up session towards the end of the 2004 season; he made his Major League debut on September 14, 2004. In his first Major League AB, he hit a home run over the Green Monster in Fenway Park off Terry Adams of the Boston Red Sox. Phillips is one of ten players to homer in his first at bat as a Yankee, along with Marcus Thames, Bubba Crosby, Todd Zeile, Wilson Betemit, Cody Ransom, Mark Reynolds, Curtis Granderson, Tyler Austin, and Aaron Judge. He became the 21st player in Major League history to hit a home run on the first pitch of his Major League career.
Also, in 2004, Phillips received the Yankees' Kevin Long "Minor-League Player of the Year" Award in a season where he led all Yankees minor leaguers in batting average (.321) and RBI (101), ranked second in home runs (30), and was voted the Most Valuable Player of the International League All Star Game after hitting a 10th inning walk-off home run. In 2005, Phillips earned the James P. Dawson Award as the Yankees' most outstanding rookie during spring training.
Phillips's time previous to 2006 at the Major League level had been limited to defensive replacement and late season call-up. In 2006, Phillips started the year as the primary backup at first base, behind Jason Giambi. This changed, however, when Gary Sheffield went on the disabled list. Primary designated hitter Bernie Williams took over the starting right field job, leaving the DH spot open. With Giambi's bad knees and his sub-par defense in the field, he became the primary DH. Phillips took over at first base and played well. This proved manager Joe Torre correct when he said all that Phillips needed was more at bats. He led the team with a .333 batting average in June and continued with his .333 average for the first 22 games of July. His average on July 26 was .300, with 30 hits in 100 at bats. Earlier, his light hitting triggered GM Brian Cashman to go out and trade for Craig Wilson of the Pittsburgh Pirates. Phillips was kept on the roster mostly because of his versatility to play second base or third base. Also, he could play first if Wilson was forced to play the outfield or catch.
A family emergency (his mother Linda was hurt in a car crash) caused Phillips to miss much of his 2007 spring training with the Yankees. In the end, he only played in 15 games, saw 26 at bats, and had a .192 average. Due to his inability to make up for lost time and Josh Phelps's (Phillips opponent for a roster spot on the Yankees) outstanding performance (spring training stats include 3 home runs, 14 hits, a .667 slugging percentage, and .389 batting average), Phillips was passed over for a roster spot on the 2007 team. When informed of manager Joe Torre's decision to go with Phelps over Phillips, Phillips reportedly thanked Torre for the opportunity and asked if Phelps had been informed of the decision yet so he could congratulate him.
Phillips was called up to the Yankees on June 19, 2007, after Phelps was designated for assignment. Throughout the 2007 season, Phillips became an important part of the team as a result of injuries to first baseman Jason Giambi and Doug Mientkiewicz. Due to these injuries, Phillips found himself used in the role of primary first baseman for the Yankees. He enjoyed great success through the months of July (hitting .320 with 16 RBI) and August (hitting .273 with 7 RBI). On September 2, while batting in the 5th inning against Devil Rays starter Jason Hammel, Phillips was hit on the wrist by a pitch. He would later leave the game and get an MRI and an X-Ray taken. It was announced on September 3 that Phillips had a fractured wrist and surgery would be required, needing 4–6 weeks, ending his season. Phillips was designated for assignment on December 3, 2007, to make room for Jose Molina. He cleared waivers on December 7, was offered an outright assignment to Triple-A Scranton, but declined the assignment and opted to become a free agent. In 2013, Andy appeared in the Old Timers Day game at Yankee Stadium.
On January 4, 2008, Phillips signed a minor league contract with the Cincinnati Reds. On March 28, after hitting .277 in 2008 spring training, he was reassigned to minor-league camp, and he began the season with the Reds' Triple-A affiliate, the Louisville Bats. On May 28, the Reds purchased his contract, and he was added to the active roster. On June 22, 2008, Phillips was designated for assignment to make room for Jeff Keppinger, who was coming off of the disabled list. Three days later, Phillips was claimed by the New York Mets and added to their 25-man roster. He was then designated for assignment by the Mets on July 1, 2008. He was reclaimed by the Cincinnati Reds off waivers on July 3.
On December 22, 2008, he signed to a minor league contract with the Pittsburgh Pirates, and was invited to Spring Training as a "non-roster invitee", the same status in which he was invited to Spring Training with the Reds in 2008. He played so well early in spring training that he was considered a lock to make the opening day roster, but a back injury sidelined him for three weeks, and he ended up assigned to Indianapolis instead.
On April 17, 2009, Phillips was traded to the Chicago White Sox in exchange for pitcher Michael Dubee, and assigned to the Charlotte Knights of the International League. He filed for free agency on June 15, 2009.
On June 23, 2009 Phillips signed with the Hiroshima Toyo Carp of Nippon Professional Baseball. Following the 2009 season, the Carp did not pick up Phillips' option for the 2010 season and he signed with the Tohoku Rakuten Golden Eagles in January 2010.
On December 22, 2010 Phillips was introduced as the Alabama Crimson Tide baseball team's hitting coach beginning in 2011.