Отец Андрея Николишина в сталинские времена был репрессирован и сослан с Украины в Воркуту, где работал на шахте и откуда в течение 25 лет не имел права выезжать. Об этом отец Андрею ничего не рассказывал, чтобы не навредить его будущей спортивной карьере. Брат родного деда Андрея эмигрировал после Первой мировой войны в Канаду, где у Андрея есть ряд родственников.
Андрей начинал как волейболист, позже увлекся хоккеем, который в итоге и выбрал как профессию.
Выступая за воркутинскую команду на финальном турнире «Золотой шайбы» в Пензе, стал лучшим бомбардиром и был признан лучшим нападающим. Знаменитый Александр Мальцев, который был на том турнире, пригласил его в московское «Динамо».
С 1990 по 1995 год играл в «Динамо»: 115 игр — 42 очка (21+21). Чемпион России 1993 года. Лучший хоккеист России 1994 года. В команде получил прозвище «Васильевич», в последние годы был капитаном команды.
В составе молодёжной сборной России стал чемпионом мира среди юниоров в 1992 году.
Чемпион мира 1993 года (8 матчей, 2+3). В 1997 году приехал на чемпионат мира без действующего контракта с клубом НХЛ и в первом же матче получил разрыв крестообразной связки колена, после чего имел ряд сложностей с оформлением трудовых отношений в НХЛ.
Выступал за национальную сборную России на Олимпийских играх 1994 года, где в 8 матчах набрал 7 очков (2+5). Бронзовый призёр Олимпиады 2002 года (6 матчей, 1 передача).
Первый гол в НХЛ — 7 марта 1995 года в матче против «Нью-Йорк Айлендерс». Участник финала Кубка Стэнли 1998 года.
Обмены — 9 ноября 1996 года был обменян из «Хартфорда» в «Вашингтон» на Кертиса Лешишина. 1 ноября 2002 года обменян из «Вашингтона» в «Чикаго» вместе с Крисом Саймоном на Микаэля Нюландера и право выбора в третьем раунде драфта. 21 июня 2003 года обменян из «Чикаго» в «Колорадо Эвеланш» на право выбора в четвёртом раунде драфта.
Локаут 2004/05 годов провел в ЦСКА (Москва), после чего продолжил свою карьеру в России.
В первом сезоне КХЛ 2008/09 набрал 39 очков (10+29) в 48 матчах за челябинский «Трактор» и добавил 9 голов в 3 поединках плей-офф на Кубок Гагарина. В сезоне 2009/10 набрал 22 очко (7+15) в 46 матчах регулярного чемпионата КХЛ и 2 матчах плей-офф.
Участник матча звёзд КХЛ (2009).
В октябре 2011 года подписал соглашение с киевским «Соколом» и выступает в Профессиональной хоккейной лиге (ПХЛ) Украины.