เลเบดเกิดที่เมืองวัลกาประเทศเอสโตเนียเขาเข้าร่วมกองทัพโซเวียตในปี 1981 โดยเริ่มรับราชการทหารในหน่วยพลร่มเขาได้รับการฝึกฝนครั้งแรกในกองพลพลร่มที่ 44 ที่ ไกซีอูไน ในสาธารณรัฐสังคมนิยมโซเวียตลิทัวเนียและต่อมาได้ประจำการในกองพลจู่โจมทางอากาศอิสระที่ 57 ที่ทัลดีคอร์กันในสาธารณรัฐ สังคมนิยมโซเวียต คาซัคสถาน^{[ 2 ]}

เขาเลือกที่จะเปลี่ยนสายอาชีพโดยเข้าเรียนที่โรงเรียนเทคนิคการบินทหารโลโมโนซอฟและสำเร็จการศึกษาเป็นวิศวกรการบินในปี 1986 เขาเข้าร่วมปฏิบัติการรบในอัฟกานิสถานในปี 1986–87 ในฐานะลูกเรือในกรมเฮลิคอปเตอร์^{[ 2 ]}ในช่วงเวลานี้เขาทำหน้าที่เป็นวิศวกรการบินในลูกเรือของหนึ่งในสี่คนที่ได้รับทั้ง ตำแหน่ง วีรบุรุษแห่งรัสเซียและวีรบุรุษแห่งสหภาพโซเวียตซึ่งในขณะนั้นคือร้อยเอกนิโคไล มายดานอฟ^{[ 3 ]}และมักมีส่วนร่วมในการปฏิบัติการภาคพื้นดินด้วยตนเอง^{[ 4 ]}

หลังจากกลับจากอัฟกานิสถาน เขาได้ปฏิบัติหน้าที่ในกลุ่มกองกำลังโซเวียตในเยอรมนีใน เขตทหาร ทรานส์-ไบคาลและไซบีเรียในกรมเฮลิคอปเตอร์ขนส่งและรบที่ 329 และในกรมเฮลิคอปเตอร์อิสระที่ 337 ตามลำดับ^{[ 2 ]}

การรับใช้ชาติของเขาทำให้เขาได้รับเครื่องราชอิสริยาภรณ์ "เพื่อการรับใช้ชาติในกองทัพ"ชั้นที่ 3 และเครื่องราชอิสริยาภรณ์ดาวแดง 3 ดวง

เขาเกษียณไปประจำการในกองกำลังสำรองในปี 1994 และทำงานให้กับกองทุนสวัสดิการทหารผ่านศึกอัฟกานิสถาน^{[ 2 ]}

เขาเข้าร่วมกลุ่มทหารผ่านศึก ชาวรัสเซีย ที่สมัครใจเข้าร่วมสงครามโคโซโว (พ.ศ. 2541–2532) ^{[ 5 ]}ในปี พ.ศ. 2542 เขาไปที่คอเคซัสเหนือในฐานะอาสาสมัครในกองกำลังผสมหลังจากซื้ออุปกรณ์ของตนเองและบินไปยังมาคาชคาลาในดาเกสถานเมื่อปฏิบัติการทางทหารเคลื่อนเข้าสู่เชชเนียในเดือนตุลาคม พ.ศ. 2542 เขาไปที่มอสโกและสมัครเข้ารับราชการอีกครั้งโดยเซ็นสัญญากับกระทรวงกลาโหมของสหพันธรัฐรัสเซียและกลับไปยังเชชเนียทันทีเพื่อเข้าร่วมปฏิบัติการต่อต้านการก่อการร้าย ตั้งแต่ปี พ.ศ. 2542 ถึง พ.ศ. 2550 เขาเดินทางไปเชชเนียมากกว่า 10 ครั้งและเข้าร่วมปฏิบัติการพิเศษในพื้นที่เมืองกูเดอร์เมสและอาร์กุนรวมถึงชานเมืองกรอซนีและภูมิภาคเวเดโน^{[ 2 ]}

ในปี พ.ศ. 2546 ขณะเข้าร่วมการสู้รบใน เทือกเขา อูลุส-เคิร์ตเขาเหยียบกับระเบิดและเสียเท้าไปข้างหนึ่ง เขาปฏิเสธที่จะลาออกจากกองทัพ ความแข็งแกร่งทางร่างกายที่เหนือกว่าของเขาทำให้เขายังคงรับราชการต่อไป ทำการกระโดดร่มต่อไป (มากกว่า 840 ครั้ง) และยังคงฝึกศิลปะการต่อสู้ด้วยขาเทียมได้^{[ 2 ]}

เมื่อวันที่ 9 มกราคม พ.ศ. 2548 หน่วยลาดตระเวนของเขาถูกซุ่มโจมตี เขาปฏิเสธที่จะปล่อยให้ทหารที่บาดเจ็บถูกจับโดยศัตรู เขาต่อสู้และเอาชนะศัตรูที่มีจำนวนมากกว่าด้วยตัวคนเดียว^{[ 2 ]}

ในการสู้รบครั้งต่อมาเมื่อวันที่ 24 มกราคม พ.ศ. 2548 เขาได้รับบาดเจ็บจากสะเก็ดระเบิดหลายจุดที่หลังขณะปกป้องลูกน้องจากแรงระเบิดของจรวด แม้จะได้รับบาดเจ็บ เขาก็ยังทำลายฐานยิงจรวดและปืนกลของศัตรูด้วยตนเอง ก่อนที่จะนำการลาดตระเวนต่อไป ส่งผลให้สามารถยึดและทำลายฐานของผู้ก่อการร้ายได้^{[ 2 ]}

เขาได้รับพระราชทานบรรดาศักดิ์วีรบุรุษแห่งสหพันธรัฐรัสเซียเมื่อวันที่ 6 เมษายน พ.ศ. 2548 โดยพระราชกฤษฎีกาของประธานาธิบดีที่ยกย่อง "ความกล้าหาญและวีรกรรมในการปฏิบัติหน้าที่ทางทหารในคอเคซัสเหนือ" ^{[ 6 ]}ในขณะนั้นเขาดำรงตำแหน่งกัปตัน

การกระทำของเขาในช่วงสงครามเซาท์ออสเซเทียปี 2008ทำให้เขาได้รับเกียรติให้เป็นอัศวินแห่งเครื่องราชอิสริยาภรณ์เซนต์จอร์จชั้นที่ 4 คนที่ สอง ^{[ 7 ]}ในพิธีมอบรางวัลเมื่อวันที่ 1 ตุลาคม 2008 ประธานาธิบดีรัสเซีย ดมิทรี เมดเวเดฟ กล่าวถึงเลเบดว่า "ในหมู่พวกเรามีเจ้าหน้าที่หน่วยรบพิเศษ วีรบุรุษแห่งสหพันธรัฐรัสเซีย อนาโตลี วยาเชสลาโววิช เลเบด เขาเป็นผู้นำจากแนวหน้าเสมอในระหว่างปฏิบัติการรบ แสดงให้เห็นถึงความกล้าหาญส่วนบุคคลที่เป็นแบบอย่างเสมอ" ^{[ 8 ]}

เลเบด ผู้ชื่นชอบการขี่ มอเตอร์ไซค์ เป็นอย่างมากเสียชีวิตจากอุบัติเหตุรถจักรยานยนต์ในกรุงมอสโกเมื่อวันที่ 27 เมษายน 2555