รับราชการอยู่ในกองบัญชาการทหารสูงสุด สังกัดกรมข่าวทหาร ได้รับพระราชทานยศพลตรี (พล.ต.) เมื่อเดือนตุลาคม พ.ศ. 2535 เป็นรองผู้บัญชาการศูนย์รักษาความปลอดภัยแห่งชาติ เมื่อ พ.ศ. 2538 เป็นรองเจ้ากรมข่าวทหาร เมื่อ พ.ศ. 2539 และรับพระราชทานยศพลโท (พล.ท.) ตำแหน่งเจ้ากรมข่าวทหารบก เมื่อ พ.ศ. 2540 และ พ.ศ. 2544 ดำรงตำแหน่งผู้บัญชาการกองกำลังรักษาสันติภาพของสหประชาชาติในติมอร์ตะวันออก

พล.อ.วินัย ได้รับพระราชทานยศพลเอก (พล.อ.) ในตำแหน่งที่ปรึกษาพิเศษ กองบัญชาการทหารสูงสุด เมื่อ พ.ศ. 2545 ก่อนจะย้ายไปดำรงตำแหน่ง เลขาธิการสภาความมั่นคงแห่งชาติ ในรัฐบาล พ.ต.ท.ทักษิณ ชินวัตร

โดยก่อนหน้านั้น พล.อ.วินัย ถือได้ว่าเป็นนายทหารที่ใกล้ชนิดสนิทสนมกับ พล.อ.อาทิตย์ กำลังเอก ในขณะที่ดำรงตำแหน่งผู้บัญชาการทหารบก ด้วยการเป็นผู้ใต้บังคับบัญชามาก่อน และเคยถูกควบคุมตัวในการรัฐประหารเมื่อวันที่ 23 กุมภาพันธ์ พ.ศ. 2534 โดยคณะรักษาความสงบเรียบร้อยแห่งชาติ (รสช.) ที่ท่าอากาศยานกองบิน 6 (สนามบิน บน.6) ของกองทัพอากาศ พร้อม พล.อ.ชาติชาย ชุณหะวัณ, พล.อ.อาทิตย์ กำลังเอก และนายพิทักษ์ อินทรวิทยนันท์

และ พล.อ.วินัย ยังสนิทสนมกับ พล.อ.สนธิ บุณยรัตกลิน มาก ในฐานะที่เป็นเพื่อนร่วมรุ่น ถึงขนาดรับประทานอาหารร่วมกันและนอนเตียงเดียวกันมาก่อน ในการรัฐประหารเมื่อวันที่ 19 กันยายน พ.ศ. 2549 พล.อ.วินัย เป็นนายทหารระดับสูงคนแรกที่ พล.อ.สนธิชักชวนมาร่วมการรัฐประหารด้วย โดย พล.อ.วินัยเป็นผู้ที่ตั้งชื่อคณะรัฐประหารครั้งนี้เองว่า "คณะปฏิรูปการปกครองในระบอบประชาธิปไตย อันมีพระมหากษัตริย์ทรงเป็นประมุข" (คปค.) โดยมีเจตนาจะให้รำลึกถึง คณะปฏิรูปการปกครองแผ่นดิน ของ พล.ร.อ.สงัด ชลออยู่ ที่เป็นญาติผู้ใหญ่ของภริยา ที่มีบทบาทในการรัฐประหารเมื่อวันที่ 6 ตุลาคม พ.ศ. 2519 และ 20 ตุลาคม พ.ศ. 2520 หลังจากนั้น บทบาทของ พล.อ.วินัย เป็นไปในลักษณะของที่ปรึกษาของคณะ คปค.และ คมช. และยังได้รับแต่งตั้งให้เป็นเลขาธิการ คมช.และได้รับโปรดเกล้าฯให้ดำรงตำแหน่งปลัดกระทรวงกลาโหม[3] จนได้รับฉายาว่า "ขงเบ้ง คมช." อีกทั้งเมื่อหลังจากที่ พล.อ.สนธิ เกษียณอายุราชการในตำแหน่ง ผบ.ทบ. มีข่าวว่า พล.อ.สนธิ แต่งตั้ง พล.อ.วินัย ให้ดำรงตำแหน่ง ผบ.ทบ.[4][5]

พลเอก วินัย ได้รับแต่งตั้งพระราชทานยศ พลเรือเอก พลอากาศเอก และแต่งตั้งเป็นนายทหารพิเศษ ประจำกรมนักเรียนนายเรือรักษาพระองค์ โรงเรียนนายเรือ และประจำกรมนักเรียนนายเรืออากาศรักษาพระองค์ โรงเรียนนายเรืออากาศ กองบัญชาการฝึกศึกษาทหารอากาศ ในปี พ.ศ. 2549[6]