Всю свою клубную карьеру провёл в английском клубе «Лидс Юнайтед», за который сыграл 531 матч. Стал первым игроком «павлинов», который в XXI веке перешагнул полутысячный рубеж игр за «белых». На нынешний момент Келли занимает восьмое место по количеству матчей за всю историю клуба.
Гэри родился 9 июля 1974 года в ирландском городе Дроэда. Он был самым младшим ребёнком из тринадцати детей семьи Келли.
Ирландец начинал играть в футбол на позиции нападающего и достаточно успешно выступал в этом амплуа за молодёжные составы клубов «Дроэда Юнайтед» и «Хоум Фарм». Однако, когда Келли перешёл в «Лидс Юнайтед», главный тренер «павлинов», Ховард Уилкинсон, быстро разглядел в Гэри задатки хорошего защитника и перевёл его на правый фланг обороны.
Дебют ирландца в «Юнайтед» состоялся в сезоне 1991/92, однако следующие два года ему пришлось завоёвывать место в основном составе клуба. В 1993 году Келли стал постоянно играть на правом фланге защиты, иногда выходя на позиции центрального защитника. К концу сезона Гэри удостоился вызова в национальную сборную Ирландии, в составе которой 23 мая 1994 года дебютировал в товарищеском матче со сборной России, 29 мая в своей четвёртой игре за «парней в зелёном» защитник забил первый мяч в сборной, поразив ворота сборной Германии. В составе ирландцев Гэри поехал на чемпионат мира 1994 в США, где сыграл два матча. В прессе троицу, состоявшую из Келли и его друзей-ровесников, Фила Бэбба и Джейсона Макатира, сразу же окрестили как «три амигос», намекая на то, что они являются закадычными приятелями, а также самыми молодыми футболистами в великовозрастной сборной «зелёных».
В сезоне 1997/98 в возрасте 23-х лет Гэри избрали капитаном «Лидс Юнайтед».
В следующем футбольном году Келли получил тяжёлую травму — перелом малоберцовой кости. Из-за этого повреждения он был вынужден пропустить весь сезон. Впоследствии эта травма мучала его на протяжении всей его футбольной карьеры.
Гэри не сдался, набрав в сезоне 1999/00 отличную форму, он вновь завоевал место в основном составе «павлинов», несмотря на серьёзную конкуренцию со стороны Дэнни Миллза — защитника сборной Англии, купленного «Лидсом» летом 1999 года.
В мае 2002 года Келли вывел «павлинов» с капитанской повязкой на выставочный матч с шотландским «Селтиком». Все доходы от этого поединка были переданы в благотворительные фонды по борьбе с раковыми болезнями — в частности, детский в Лидсе и общеирландский в Дроэде. Матч был инициирован и организован самим Гэри в память о его сестре Мэнди, скончавшейся от онкологического заболевания в 1998 году. Поединок собрал аудиторию в 26 440 человек.
В этом же году Келли представлял ирландскую сборную на мировом чемпионате, где отыграл все четыре матча команды на этом турнире. Проведя за «парней в зелёном» 52 встречи и забив 2 гола, 26 сентября 2003 года Гэри объявил о завершении международной карьеры.
25 февраля 2006 года, сыграв матч за «Юнайтед» против «Лутон Таун», Гэри стал десятым футболистом в истории «Лидса», которому покорился рубеж в 500 игр за клуб.
Первую половину своего 16-го сезона за «павлинов» Келли провёл уверенно, регулярно выходя в стартовом составе команды. Затем однако ирландец повздорил с новым президентом «белых», Кеном Бейтсом, и наставником «Лидса», Деннисом Уайзом. 26 октября 2006 года Уайз объявил, что он снимает с Гэри обязанности вице-капитана команды, назначив на эту должность Шона Дерри. После этого ирландец заявил, что покинет клуб по окончании сезона.
После последнего домашнего матча сезона 2006/07 легенды «Лидса», такие как Пол Рини, Аллан Кларк, Мик Джонс и Фрэнк Уортингтон, вручили Келли хрустальную вазу в знак признательности от всех людей, причастных к клубу, за его верную шестнадцатилетнюю карьеру в «Юнайтед». После того, как Гэри покинул «павлинов», он решил закончить карьеру футболиста.
Келли является родным дядей другого знаменитого футболиста «Лидс Юнайтед», Иана Харта. Они вместе играли за йоркширский клуб, а также защищали цвета Ирландии на чемпионате мира 2002 года.
В сентябре 2010 года Гэри вместе со своим братом Джимом предстал перед судом за нападение на трёх человек.
В свою бытность игроком «Лидса» и сборной Ирландии Келли прослыл неувядаемым шутником и балагуром. В частности, многие игроки «Юнайтед» вспоминают проказу Гэри над будущей поп-звездой группы «Westlife», Никки Бирном, который в то время был ещё начинающим голкипером. Перед одной из тренировок Келли облачился во вратарскую амуницию Бирна и всю тренировку провёл в воротах команды. Главный тренер «Лидса» Дэвид О’Лири включился в розыгрыш и, как будто не заметив подмены, «гонял» Никки всю тренировку по упражнениям полевых игроков, к которым, конечно, вратарь был не готов. Бирн оказался не обидчивым человеком — они быстро сдружились с Гэри. После этого каждый забитый гол Келли на занятиях они стали праздновать сценкой, где Никки «чистил» бутсы защитника.
Однажды Гэри, из-за травмы не принимавший участие в матче чемпионата Англии, выпросил у администрации «Элланд Роуд» костюм талисмана клуба кота Лукаса, и, одевшись в него, всю игру «заводил» фанатов «Лидса».
Итого: 52 матча / 2 гола; 24 победы, 14 ничьих, 14 поражений.
«Лидс Юнайтед»