У дорослому футболі Енді Грей дебютував 1973 року виступами за команду клубу «Данді Юнайтед», в якій провів два сезони, взявши участь у 62 матчах чемпіонату. А в сезоні 1974-75 поділив звання найкращого бомбардира Першого дивізіону з Віллі Петтігрю, забивщи 20 голів.
У жовтні 1975, у віці 19 років, Енді переїхав на південь в «Астон Віллу», яка щойно вийшла в Перший дивізіон. В першомуж сезоні за «Віллу» він став найкращим бомбардиром сезону 1976-77, забивши 25 голів в чемпіонаті. Завдяки своїм 29 голам в усіх турнірах за сезон він став найкращим молодим гравцем року та гравцем року за версією ПФА. Такий дубль змогли повторити лише Кріштіану Роналду через 30 років та Гарет Бейл в 2013 році. На той час Грей був наймолодшим гравцем року і єдиним гравцем , який здобув три офіційні нагороди за сезон.
У вересні 1979 Грей перейшов до місцевого противника «Астон Вілли» «Вулвергемптона» за рекордні на той час для Англії £1,500,000. Після забитого переможного голу у фіналі Кубка англійської ліги 1979-80 він залишився з Вулвз аж до їхного вильоту в Другий дивізіон і повернення роком пізніше, незважаючи на інтерес з боку «Манчестер Юнайтед».
Ендрю переїхав в «Евертон» в листопаді 1983 за £250,000. Він провів два сезони в мерсисайдському клубі, спершу здобувши Кубок Англії в травні 1984. У фіналі проти Вотфорда він забив спірний гол, вибивши м'яч з рук воротаря суперників. Рік потому він став чемпіоном Англії і виграв Кубок Кубків УЄФА, забивши віденському «Рапіду» у фіналі. Грей з командою також дійшов до іншого фіналу Кубка Англії, але цього разу «Евертон» був розбитий «Манчестер Юнайтед». В міжсезонні 1985 року в «Евертон» перейшов з «Лестер Сіті» нападник збірної АнгліїГарі Лінекер, який витіснив Енді Грея з основного складу. Незважаючи на гнівні петиції від фанів «Евертона», охочих зберегти його на «Гудісон Парк», він покинув клуб 10 липня 1985, повернувшись до «Астон Вілли» за £150,000.
Незважаючи на високий рівень гри на початку десятиліття, «Вілла» була середняком Вищого дивізіону і повернення Грея не могло змінити ситуацію настільки, як його прихід в «Евертон». Він забив п'ять голів у 35 матчах в 1985-86 роках, тоді як «Астон Вілла» ледве уникла вильоту в Другий дивізіон, а в наступному сезоні він не зміг забити жодного гола в 19 матчах і команда вилетіла з Першого дивізіону. Сезон 1987-88 він почав ще у «Віллі», але був відправлений в оренду до «Вест Бромвіч Альбіон» у вересні 1987. Він провів в «Вест Бромвіч» менше року. Тоді клубу ледве вдалося уникнути вильоту з Другого дивізіону.
У середині 1988 року Грей приєднався до «Рейнджерс». Він провів один сезон на «Айброкс», допомігши їм виграти перший з дев'яти поспіль виграних титулів чемпіона Шотландії.
Енді Грей завершив ігрову кар'єру у напівпрофесійному клубі «Челтнем Таун», за команду якого виступав з 1989 по 1990 рік.
