แลร์รี่ เมย์ ลงเล่นเป็นเซ็นเตอร์แบ็คให้กับ เลสเตอร์ ซิตี้ ระหว่างปี 1977-1983 โดยทำสถิติลงสนาม 199 นัด เมย์มีการป้องกันที่แข็งแกร่งและทักษะการเล่นเกมรับที่ยอดเยี่ยม เขามีความแข็งแกร่งในการดวลลูกกลางอากาศ เป็นนักแท็คเกิลที่ทรงพลัง และมีความเร็ว อีกทั้งยังชื่นชอบการขึ้นไปเล่นลูกตั้งเตะ และทำประตูสำคัญให้กับทีมได้หลายครั้ง
จิมมี่ บลูมฟิลด์ เป็นผู้ให้โอกาส แลร์รี่ เมย์ ประเดิมสนามในเกมลีกสูงสุดพบกับ บริสตอล ซิตี้ ในเดือนมีนาคมปี 1977 ตอนที่เขาอายุเพียง 18 ปี แต่ในฤดูกาลถัดมา ภายใต้การคุมทีมของผู้จัดการทีมคนใหม่ แฟรงค์ แม็คลินท็อค การพัฒนาของแลร์รี่ ต้องสะดุดลงเนื่องจากการผ่าตัดหมอนรองกระดูกหัวเข่าติดต่อกันถึงสองครั้ง
อย่างไรก็ตาม จ็อค วอลเลซ ซึ่งเข้ามาเป็นผู้จัดการทีมในเดือนมิถุนายนปี 1978 ประทับใจในบุคลิกและจิตใจที่มุ่งมั่นของแลร์รี่ และตัดสินใจให้เขาเป็นหัวใจสำคัญในแนวรับของทีม
ในฤดูกาล 1978/79 วอลเลซให้ แลร์รี่ เมย์ จับคู่เป็นเซ็นเตอร์แบ็คกับ จอห์น โอนีล และทั้งคู่กลายเป็นกำลังสำคัญในแนวรับของทีมเป็นเวลาถึง 5 ปี ช่วงแรกทีมของวอลเลซ ยังขาดประสบการณ์ โดยมีนักเตะดาวรุ่งอย่าง แกรี่ ลินิเกอร์, เดฟ บูคานัน และแอนดี้ พีค ที่ยังต้องการเวลาเรียนรู้
แต่ในฤดูกาลถัดมา (1979/80) เลสเตอร์ ซิตี้ สามารถคว้า แชมป์ดิวิชัน 2 และเลื่อนชั้นกลับสู่ลีกสูงสุดโดย แลร์รี่ ลงเล่นทุกนัดในฤดูกาลนั้นและทำได้ 4 ประตู หนึ่งในนั้นคือประตูชัยในเกมสุดท้ายของฤดูกาลที่พบกับ โอเรียนท์ ซึ่งทำให้ทีมคว้าแชมป์ได้สำเร็จ
ฤดูกาล 1980/81 ทีมกลับมาสู่ลีกสูงสุดด้วยความหวังที่จะรักษาสถานะในลีกสูงสุดต่อไป แต่โชคร้ายที่สุดท้ายต้องตกชั้น อย่างไรก็ตาม แลร์รี่ ยังคงเป็นกำแพงเหล็กในแนวรับของทีม หนึ่งในไฮไลต์สำคัญของฤดูกาลนั้น คือการที่ เลสเตอร์ ซิตี้ สามารถเอาชนะ ลิเวอร์พูล ทั้งเหย้าและเยือน โดยที่ลิเวอร์พูล เป็นทีมที่คว้าแชมป์ยูโรเปียน คัพ ได้ในฤดูกาลนั้น
ในฤดูกาล 1981/82 แลร์รี่ และ จอห์น โอนีล ยังคงเป็นแกนหลักของทีมและ พาทีมเข้าถึงรอบรองชนะเลิศของ เอฟเอ คัพ แลร์รี่ ยิงประตูชัยในรอบที่ 4 กับ เฮเรฟอร์ด ยูไนเต็ด ทำประตูแรกในเกมชนะชรูว์สบิวรี่ ทาวน์ 5-2 ซึ่งเป็นแมตช์ที่ เลสเตอร์ ซิตี้ ต้องใช้ผู้รักษาประตู 3 คนในเกมเดียวกัน
หลังจบฤดูกาลนั้น จ็อค วอลเลซ อำลาสโมสร และถูกแทนที่โดย กอร์ดอน มิลน์ ในฤดูกาล 1982/83 แลร์รี่และโอนีล ยังคงเป็นคู่หูในแนวรับ และช่วยให้ เลสเตอร์ ซิตี้ จบอันดับ 3 พร้อม เลื่อนชั้นกลับสู่ลีกสูงสุด อย่างไรก็ตามแฟนบอลต้องช็อกเมื่อ มิลน์ตัดสินใจขายแลร์รี่ ให้กับบาร์นสลีย์ในราคา 110,000 ปอนด์ หลังออกจากเลสเตอร์ แลร์รี่ได้ย้ายไปค้าแข้งให้กับ เชฟฟิลด์ เว้นส์เดย์ และไบรท์ตัน แอนด์ โฮฟ อัลเบี้ยน
การจากไปของ แลร์รี่ เมย์ ทำให้แฟนๆ เสียใจอย่างมาก เขาเป็นนักเตะขวัญใจของกองเชียร์ตลอดช่วงเวลาที่อยู่กับทีม การป้องกันที่แข็งแกร่ง การเล่นที่ดุดัน และหัวใจที่ทุ่มเท ทำให้เขาเป็นหนึ่งในกองหลังที่ดีที่สุดที่เคยลงเล่นให้กับ เลสเตอร์ ซิตี้