เมื่อวันที่ 28 กันยายน ปี 1985 แกรี่ แม็คอัลลิสเตอร์ ลงสนามเปิดตัวให้กับเลสเตอร์ ซิตี้ ในเกมพบกับ อิปสวิช ทาวน์ ในศึกดิวิชันหนึ่งยุคเก่า และต่อมาเขากลายเป็นหนึ่งในกองกลางที่เล่นได้สวยงามและชาญฉลาดที่สุดที่เคยเล่นให้กับทีมจิ้งจอกสยาม
ในช่วงวัยเด็ก แม็คอัลลิสเตอร์ เคยได้รับความสนใจจาก แมนเชสเตอร์ ยูไนเต็ด แต่สุดท้ายดีลไม่เกิดขึ้น และเขาเลือกเซ็นสัญญากับ มอเธอร์เวลล์ แทน เขาถูกดันขึ้นทีมชุดใหญ่ตั้งแต่อายุ 16 ปี และช่วยทีมเลื่อนชั้นได้สำเร็จ
ในเดือนสิงหาคม ปี 1985 ขณะอายุ 20 ปี แกรี่ แม็คอัลลิสเตอร์ ถูกเซ็นสัญญาโดยผู้จัดการทีม กอร์ดอน มิลน์ ด้วยค่าตัว 250,000 ปอนด์ ซึ่งเป็นดีลที่รวม อาลี มอชเลน มาร่วมทีมด้วย
ขณะนั้น เลสเตอร์ ซิตี้ อยู่อันดับรองสุดท้ายของตาราง และเกมเปิดตัวของ แม็คอัลลิสเตอร์ คือเกมที่ 10 ของฤดูกาล และทีมก็คว้าชัยชนะสำคัญ 1-0 เก็บสามแต้มได้
แม็คอัลลิสเตอร์ โชว์การสัมผัสบอลที่นุ่มนวล การจ่ายบอลที่ยอดเยี่ยมให้กับ สตีฟ ไลเน็กซ์ และเขายังทดสอบผู้รักษาประตูของ อิปสวิช ด้วยลูกยิงจากนอกกรอบเขตโทษหลายครั้ง นอกจากนี้ เขายังทำแอสซิสต์ด้วยการจ่ายบอลทะลุแนวรับที่เฉียบขาด
จากฟอร์มที่โดดเด่นในเกมแรก ทำให้เขากลายเป็นตัวเลือกแรกในแผงกองกลางของเลสเตอร์ ตลอดห้าฤดูกาล ลงเล่นไป 225 นัด และยิงได้ 51 ประตู โดยบางลูกเป็นลูกยิงไกลสุดสวย เขาสามารถเล่นได้ทั้งมิดฟิลด์ตัวกลางและริมเส้น และกลายเป็นผู้เชี่ยวชาญลูกตั้งเตะ
การจ่ายบอลที่แม่นยำของเขา ทั้งระยะสั้นและยาว สร้างโอกาสมากมายให้กับกองหน้าเพื่อนร่วมทีม โดยเฉพาะ อลัน สมิธ อดีตดาวยิงของทีมที่ภายหลังย้ายไปเป็นสตาร์ดังของ อาร์เซนอล และทีมชาติอังกฤษ
ฤดูกาลแรกของ แม็คอัลลิสเตอร์ ที่ ฟิลเบิร์ต สตรีท เป็นช่วงเวลาที่ยากลำบากสำหรับสโมสร แม้ทีมจะตกชั้นในปีถัดมา แต่ฟอร์มของเขายังคงโดดเด่น
ในช่วงสามฤดูกาลสุดท้ายของเขาที่สโมสร แม้ว่าทีมจะต้องดิ้นรนในดิวิชันสองแต่ แม็คอัลลิสเตอร์ กลับเป็นนักเตะที่เปล่งประกายที่สุดในทีม
ฟอร์มของเขาทำให้เขาถูกเรียกติดทีมชาติสกอตแลนด์ ในปี 1990 ซึ่งเป็นฤดูกาลสุดท้ายของเขากับเลสเตอร์ และในช่วง 9 ปีต่อมา เขาติดทีมชาติถึง 57 นัด และสวมปลอกแขนกัปตันทีมชาติเป็นเวลา 4 ปี
สุดท้ายสิ่งที่หลีกเลี่ยงไม่ได้ก็เกิดขึ้น ในเดือนมิถุนายน ปี 1990 แม็คอัลลิสเตอร์ ตัดสินใจย้ายกลับไปเล่นในลีกสูงสุดอีกครั้ง ด้วยการเซ็นสัญญากับ ลีดส์ ยูไนเต็ด ด้วยค่าตัว 1 ล้านปอนด์ และคว้าแชมป์ลีกสูงสุดในปี 1992
จากนั้นเขายังค้าแข้งในลีกสูงสุดต่อไปกับ โคเวนทรี ซิตี้ และ ลิเวอร์พูล โดยที่ ลิเวอร์พูล เขาคว้าทริปเปิลแชมป์ ได้แก่ ลีกคัพ, เอฟเอ คัพ และ ยูฟ่า คัพ ในปี 2001
ภายหลังแขวนสตั๊ด แม็คอัลลิสเตอร์ หันมารับงานโค้ช โดยเคยเป็นผู้จัดการทีมของ โคเวนทรี ซิตี้ และ ลีดส์ ยูไนเต็ด นอกจากนี้ เขายังเคยเป็นผู้ช่วยผู้จัดการทีมที่ แอสตัน วิลล่า และ กลาสโกว์ เรนเจอร์ส ถึงสองครั้ง
แม้ว่าความสำเร็จของเขาจะเกิดขึ้นกับหลายสโมสร แต่เลสเตอร์ ซิตี้ คือที่ที่เขาแจ้งเกิดในฐานะนักเตะระดับท็อป และทำให้เขากลายเป็นหนึ่งในกองกลางที่ดีที่สุดของยุค