Футбольная карьера Гари началась в его родном городе Мотеруэлле, где он выступал за одноимённый футбольный клуб. Он провёл там несколько отличных сезонов, пока в 1985 году его отличное выступление в полуфинале Кубка Шотландии против Селтика не привлекло внимание менеджера Лестер Сити Гордона Милна. Вскоре трансфер Макаллистера был выкуплен англичанами за общую сумму 250 тысяч фунтов.

1990 год стал переломным для карьеры Гари Макаллистера — он не только сменил Лестер на более серьёзный клуб Лидс, который смог пробиться в Первый дивизион, но и стал, наконец, регулярно вызываться в сборную Шотландии. Первый сезон Макаллистера на Элланд Роуд можно занести команде в актив — Лидс занял итоговое четвёртое место и дошёл до полуфинала Кубка Лиги — весьма неплохой результат для команды, которая ещё год назад играла во Втором Дивизионе.

Тогда же сформировалась отличная связка полузащитников Лидса — Гари Макаллистер и Гордон Страхан, которой помогали относительно молодые Дэвид Бэтти и Гари Спид. Пожалуй, именно центральная линия, ставшая настоящим «сплавом молодости и опыта», сыграла решающую роль в чемпионстве Лидса 1991—1992 годов.
С 1996 по 2000 год Гари выступал за Ковентри, которым сначала руководил Рон Аткинсон, а затем бывший партнёр Макаллистера по Лидсу Гордон Страхан. На это время приходится и окончание карьеры 33 летнего Гари в сборной, за которую он в последний раз сыграл в 1998 году, проведя в общей сложности 57 официальных матчей.

В 2000 году тридцатипятилетний Гари Макаллистер потряс футбольную общественность, перейдя из Ковентри в Ливерпуль. Большая часть болельщиков недоумевала, потому что покупка Жераром Улье футболиста, который уже давно перешагнул рубеж в тридцать лет. Макаллистер отыграл за Ливерпуль лишь два сезона, но сумел стать за это недолгое время кумиром фанов команды и помог "Красным" пополнить коллекцию трофеев на Энфилде. Гари не только принял участие в успешном походе Ливерпуля за Кубком Лиги, Кубком Англии и Кубком УЕФА, но и оказал влияние на целое поколение мерсисайдских игроков.

Гари, известный своим умением исполнять стандарты, регулярно демонстрировал своё мастерство, отметившись, в частности, потрясающим ударом с дальней дистанции в матче против принципиальных соперников Ливерпуля из Эвертона, который сделал его одним из персонажей энфилдского фольклора, а также голом, который принёс его команде победу в Кубке УЕФА. Основное время финального матча, проходившего в Дортмунде, завершилось вничью 4—4, а в дополнительное время судьбу трофея решил «золотой гол». Макаллистер ударом со штрафного отправил мяч в дальний угол, но защитник испанского Алавеса срезал снаряд в собственные ворота, и в результате, гол был записан именно на его имя.
Многие болельщики Ливерпуля до сих пор сожалеют о том, что Макаллистер пришёл в их клуб на десять лет "позже, чем должен был".

После ухода из Ливерпуля Макаллистер в течение одного сезона был играющим тренером Ковентри, но затем был вынужден покинуть эту должность по семейным обстоятельствам, когда у его жены Дэнис обнаружили рак молочной железы, которая скончалась в 2006 году.

В 2002 году Макаллистер был удостоен звание члена Ордена Британской Империи.