นิโคไล อีวาโนวิช เยจอฟเป็นรัฐมนตรีว่าการกระทรวงมหาดไทย (People’s Commissariat for Internal Affairs–NKVD) และผู้อำนวยการหน่วยตำรวจลับหรือคณะกรรมาธิการความมั่นคงแห่งรัฐ (State Security Committee) ซึ่งเรียกกันทั่วไปว่า เคจีบี (KGB)* แม้เยจอฟจะได้เข้าร่วมเคลื่อนไหวทางการเมืองกับกรรมกรหัวก้าวหน้าซึ่งส่วนใหญ่เป็นสมาชิกพรรคบอลเชวิค (Bolsheviks)* แต่เขายังไม่ได้เข้าเป็นสมาชิกพรรคจนถึงต้นเดือนพฤษภาคม ค.ศ. ๑๙๑๗ ในช่วงสงครามกลางเมืองรัสเซีย (Russian Civil War ค.ศ. ๑๙๑๘–๑๙๒๑)* เยจอฟมีโอกาสรู้จักกับโจเซฟ สตาลิน (Joseph Stalin)* รัฐมนตรีว่าการกิจการประชาชาติ (People’s Commissariat for Nationalities Affairs)ในเวลาต่อมาสตาลินจึงสนับสนุนเขาให้ก้าวหน้าในอาชีพการงานและเป็นสมาชิกคณะกรรมาธิการกลางของพรรคคอมมิวนิสต์โซเวียตเมื่อเซียร์เกย์ มีโรโนวิช คีรอฟ (Sergey Mironovich Kirov)* เลขาธิการพรรคคอมมิวนิสต์โซเวียตสาขาเลนินกราดถูกลอบสังหารอย่างมีเงื่อนงำใน ค.ศ. ๑๙๓๔ สตาลินให้เยจอฟสร้างหลักฐานเท็จใส่ร้ายป้ายสีศัตรูทางการเมืองของเขาเพื่อจับกุมกวาดล้าง และต่อมาแต่งตั้งเยจอฟเป็นรัฐมนตรีว่าการกระทรวงมหาดไทย (๒๖ กันยายน ค.ศ. ๑๙๓๖–๒๗ มกราคม ค.ศ. ๑๙๓๗) และหัวหน้าตำรวจลับ (๒๗ มกราคม ค.ศ. ๑๙๓๗–๒๕ พฤศจิกายน ค.ศ. ๑๙๓๘) เยจอฟจึงใช้เหตุการณ์ลอบสังหารคีรอฟกำจัดศัตรูทางการเมืองของสตาลินทั้งฝ่ายพลเรือน ทหาร และสมาชิกพรรคซึ่งนำไปสู่การกวาดล้างครั้งใหญ่ (Great Purges)* ระหว่าง ค.ศ. ๑๙๓๗–๑๙๓๘ การปราบปรามกวาดล้างอันนองเลือดที่มีเยจอฟเป็นผู้ควบคุมสั่งการทำให้ช่วงเวลาดังกล่าวเรียกว่า “สมัยเยจอฟ” (Yezhovshchina; Yezhov Era)

 เยจอฟเกิดในครอบครัวกรรมกรซ่อมถนนที่กรุงเซนต์ปีเตอร์สเบิร์ก (St. Petersburg) เมื่อวันที่ ๑ พฤษภาคม ค.ศ. ๑๘๙๕ ครอบครัวหาเช้ากินค่ำและมีชีวิตที่ยากลำบาก เยจอฟจึงไม่มีโอกาสเรียนหนังสือและต้องลาออกมาหางานทำเพื่อจุนเจือครอบครัวตั้งแต่อายุ ๙ ปี เขาเป็นลูกมือฝึกงานตามโรงงานต่าง ๆ ทั่วกรุงเซนต์ปีเตอร์สเบิร์กเยจอฟไม่มีเพื่อนและเป็นคนเงียบ ๆ ทั้งมีนิสัยชอบความรุนแรง เขามักจับแมวมาแกล้งด้วยการผูกผ้าหรือกระดาษชุบน้ำมันไว้ที่หางแล้วจุดไฟให้แมวตกใจวิ่งหนีจนตาย เขาสูงประมาณ ๑๕๑ เซนติเมตรแต่กำยำ และด้วยนิสัยชอบความรุนแรงทำให้เยจอฟในเวลาต่อมาได้สมญาว่า “คนแคระกระหายเลือด” (Bloody Dwarf) ใน ค.ศ. ๑๙๑๔ ขณะอายุ ๑๙ ปีเขาทำงานที่โรงงานปูตีลอฟสกี (Putilovsky) ซึ่งได้ชื่อว่าเป็นโรงงานที่มีกรรมกรหัวก้าวหน้าจำนวนมาก และส่วนใหญ่เป็นสมาชิกพรรคการเมืองฝ่ายซ้ายเยจอฟจึงถูกโน้มน้าวให้เข้าร่วมกลุ่มศึกษาการเมืองในโรงงาน ซึ่งทำให้เขาสนใจแนวความคิดสังคมนิยมทั้งเริ่มรู้จักชื่อของคาร์ล มากซ์ (Karl Marx)* และวลาดีมีร์ เลนิน (Vladimir Lenin)* ระหว่างค.ศ. ๑๙๑๔–๑๙๑๕ เยจอฟเข้าร่วมเคลื่อนไหวนัดหยุดงานและชุมนุมต่อต้านการขาดแคลนอาหารและราคาสินค้าที่เพิ่มสูงมากขึ้นอันเป็นผลสืบเนื่องจากสงครามโลกครั้งที่ ๑ (First World War)* ที่รัสเซียเข้าร่วม หลังยุทธการที่ทันเนนแบร์ก (Battle of Tannenberg ๒๖–๓๑ สิงหาคม ค.ศ. ๑๙๑๔)* รัสเซียเริ่มเป็นฝ่ายเพลี่ยงพล้ำในต้น ค.ศ. ๑๙๑๕ รัสเซียระดมพลครั้งใหม่และเยจอฟถูกเกณฑ์เป็นทหารไปรบในแนวหน้า

 เมื่อเกิดการปฏิวัติเดือนกุมภาพันธ์ (February Revolution)* ค.ศ. ๑๙๑๗ ในกรุงเปโตรกราด (Petrograd) ซาร์นิโคลัสที่ ๒ (Nicholas II)* ทรงให้ถอนกำลังบางส่วนจากแนวหน้ามาสมทบกองกำลังที่กรุงเปโตรกราดเพื่อปราบปรามการจลาจล เยจอฟได้กลับมากรุงเปโตรกราดด้วย และได้รับการติดต่อจากเพื่อนกรรมกรให้รายงานข่าวการเคลื่อนไหวของกองทัพเขาร่วมเคลื่อนไหวกับพรรคเมนเชวิค (Mensheviks)* ในการผลักดันการจัดตั้งสภาโซเวียตเปโตรกราดขึ้นต่อมาเมื่อซาร์นิโคลัสที่ ๒ ทรงถูกสมาชิกสภาดูมา (Duma)* กดดันและบังคับให้สละราชย์ในวันที่ ๑ มีนาคมค.ศ. ๑๙๑๗ทำให้มีการจัดตั้งรัฐบาลเฉพาะกาลขึ้นปกครองร่วมกับสภาโซเวียต เยจอฟซึ่งถูกปลดประจำการจากกองทัพจึงเข้าเป็นสมาชิกพรรคบอลเชวิคและร่วมเคลื่อนไหวเพื่อโค่นอำนาจรัฐบาลเฉพาะกาล

 หลังพรรคบอลเชวิคยึดอำนาจทางการเมืองได้ในการปฏิวัติเดือนตุลาคม (October Revolution)* ค.ศ. ๑๙๑๗ รัสเซียเปลี่ยนการปกครองเป็นระบอบสังคมนิยมและเปลี่ยนชื่อประเทศเป็นสหพันธ์สาธารณรัฐโซเวียตสังคมนิยมรัสเซีย (Russian Socialist Federative Soviet Republic–RSFSR)* ใน ค.ศ. ๑๙๑๘ และดำเนินนโยบายถอนตัวออกจากสงครามประเทศสัมพันธมิตรจึงสนับสนุนฝ่ายต่อต้านการปฏิวัติหรือฝ่ายรัสเซียขาวจัดตั้งกองทัพรัสเซียใต้ขึ้นโดยมีพลเอก อันตอน เดนีกิน (Anton Denikin)* เป็นผู้บังคับบัญชา เยจอฟจึงสมัครเป็นทหารในกองทัพแดง (Red Army)* ในระหว่างสงครามกลางเมืองรัสเซียเขามีโอกาสพบและรู้จักกับสตาลิน รัฐมนตรีว่าการกิจการประชาชาติซึ่งขณะนั้นดำรงตำแหน่งเป็นผู้บัญชาการกองทัพแดงในแถบยูรัลด้วย สตาลินพอใจในบุคลิกภาพและความเอาการเอางานของเยจอฟการรู้จักกันครั้งนี้จึงวางรากฐานความสัมพันธ์ระหว่างคนทั้งสองและเปิดทางให้เยจอฟได้ก้าวหน้าในงานอาชีพในเวลาต่อมา

 หลังสงครามกลางเมืองสิ้นสุดลง เยจอฟทำงานเป็นนายทหารคอมมิสซาร์หรือทหารการเมือง (political commissar) ประจำหน่วยวิทยุโทรเลขที่คาซาน (Kazan) และในช่วงต้นทศวรรษ ๑๙๒๐ ย้ายไปสังกัดหน่วยงานพรรคอีกหลายแห่ง ใน ค.ศ. ๑๙๒๗ เขาโอนไปสังกัดหน่วยงานบริหารบุคคลของคณะกรรมาธิการกลางพรรคคอมมิวนิสต์โซเวียตที่กรุงมอสโกซึ่งเขาได้พบรักกับเยฟเกเนีย เฟย์เกนเบียร์ก (Yevgenia Feigenberg) สมาชิกพรรค ก่อนหน้านั้นเยจอฟแต่งงานกับอันโตเนีย ตีโตวา (Antonia Titova) สาวโรงงานใน ค.ศ. ๑๙๑๙ แต่ชีวิตคู่ไม่ราบรื่นและหย่าขาดกัน เขาแต่งงานกับเฟย์เกนเบียร์กในเวลาต่อมาแต่ไม่มีบุตรด้วยกันทั้งสองจึงไปขอรับเด็กหญิงกำพร้ามาอุปการะและตั้งชื่อว่านาตาชา (Natasha) ในช่วงที่ทำงานอยู่ที่กรุงมอสโกสตาลินสนับสนุนเขาให้ก้าวหน้าในหน้าที่การงานระหว่าง ค.ศ. ๑๙๒๙–๑๙๓๐ เยจอฟเป็นผู้ช่วยรัฐมนตรีว่าการกระทรวงเกษตรและผู้อำนวยการหน่วยงานต่าง ๆ ของพรรคคอมมิวนิสต์ เช่น ผู้อำนวยการฝ่ายกิจการพิเศษ ฝ่ายบริหารงานบุคคล ฝ่ายอุตสาหกรรมต่อมาใน ค.ศ. ๑๙๓๔ เยจอฟ นีกีตา ครุชชอฟ (Nikita Khrushchev)* และเกออร์กี มาเลนคอฟ (Georgi Malenkov)* ซึ่งได้ชื่อว่าเป็นสหายที่สตาลินไว้วางใจได้เข้าเป็นสมาชิกคณะกรรมาธิการกลางพรรคคอมมิวนิสต์ ในปีต่อมาเยจอฟได้เป็นเลขาธิการคณะกรรมาธิการกลางพรรคคอมมิวนิสต์ ระหว่างเดือนกุมภาพันธ์ ค.ศ. ๑๙๓๕ ถึงเดือนมีนาคม ค.ศ. ๑๙๓๙ เขายังดำรงตำแหน่งประธานของคณะกรรมการกลางเพื่อการควบคุมแห่งพรรค (Central Commission for Party Control) ด้วย

 ในต้นเดือนธันวาคม ค.ศ. ๑๙๓๔ เซียร์เกย์ คีรอฟ เลขาธิการพรรคคอมมิวนิสต์โซเวียตสาขาเลนินกราดถูกลอบสังหารที่สมอลนืย (Smolny) ศูนย์บัญชาการของพรรคคอมมิวนิสต์โซเวียตเลนินกราดโดยเสียชีวิตอย่างมีเงื่อนงำ สตาลินประกาศแข็งกร้าวที่จะดำเนินการปราบปรามกลุ่มผู้อยู่เบื้องหลังการตายของคีรอฟและเห็นเป็นโอกาสใช้เหตุการณ์นี้เป็นข้ออ้างจับกุมและกำจัดศัตรูทางการเมืองทั้งฝ่ายพลเรือน ทหาร และสมาชิกพรรค เขามอบหมายให้เยจอฟสร้างหลักฐานเท็จใส่ร้าย เลฟ โบรีโซวิช คาเมเนฟ (Lev Borisovich Kamenev)* และกรีกอรี เยฟเซเยวิช ซีโนเวียฟ (Grigori Yevseyevich Zinoviev)* ผู้นำบอลเชวิคปีกขวาและพลพรรคว่าเป็นกลุ่มต่อต้านแห่งเลนินกราดที่อยู่เบื้องหลังการลอบสังหาร คนทั้งสองถูกพิจารณาคดีในเดือนมกราคม ค.ศ. ๑๙๓๕ และถูกตัดสินจำคุกทั้งต้องถูกพิจารณาคดีอย่างเปิดเผยต่อสาธารณชนอีกครั้งใน ค.ศ. ๑๙๓๖ ความสำเร็จของเยจอฟในการปรักปรำคาเมเนฟและซีโนเวียฟทำให้สตาลินพอใจมาก

 ในช่วงนั้นรัฐมนตรีว่าการกระทรวงมหาดไทยคือ เกนริค ยาโกดา (Genrikh Yagoda) เขาเป็นนักปฏิวัติบอลเชวิคเชื้อสายยิวซึ่งแต่งงานกับอีดา เอเวียร์บัค (Ida Averbach) หลานสาวของยาคอฟ สเวียร์ดลอฟ (Yakov Sverdlov)* ประธานคณะกรรมการบริหารกลางรัสเซียทั้งมวลแห่งโซเวียต (All Russian Central Executive Committee of the Soviet Congress) สเวียร์ดลอฟจึงสนับสนุนเขาให้มีตำแหน่งหน้าที่สำคัญในองค์การพรรคจนได้เป็นรองหัวหน้าหน่วยเชกา (CHEKA)* และคนสนิทของเฟลิกซ์ ดเซียร์จินสกี (Felix Dzerzhinsky)* หัวหน้าตำรวจลับและรัฐมนตรีว่าการกระทรวงคมนาคม ยาโกดามีบทบาทสำคัญในการเกณฑ์แรงงานนักโทษจากค่ายกักกันแรงงาน (Collective Labour Camp)* สร้างคลองเชื่อมระหว่างทะเลขาวกับทะเลบอลติกระหว่าง ค.ศ. ๑๙๓๑–๑๙๓๓ จนสำเร็จและได้รับอิสริยาภรณ์เลนิน (Order of Lenin) เขายังได้รับมอบหมายให้ควบคุมการขุดคลองเชื่อมระหว่างกรุงมอสโกกับแม่น้ำวอลกา แต่ดำเนินการไม่สำเร็จเพราะเขาถูกโค่นอำนาจก่อนและเยจอฟรับสานการดำเนินงานต่อจนสำเร็จ

 ยาโกดาได้ชื่อว่าเป็นคนโหดเหี้ยมและเลือดเย็นเนื่องจากเขาเคยรับผิดชอบในการสั่งฆ่าพลเมืองยูเครนเกือบ ๑๐ ล้านคนที่ต่อต้านอำนาจรัฐโซเวียต เมื่อคีรอฟถูกลอบสังหาร สตาลินออกกฤษฎีกาฉุกเฉินหลายฉบับให้อำนาจยาโกดาในการจับกุมไต่สวนและพิจารณาคดีทั้งประหารชีวิตบุคคลที่ต้องสงสัยว่ามีส่วนเกี่ยวข้องหรือสังกัดในองค์การก่อการร้ายได้ทันที หลังการสังหารคีรอฟได้ ๓ สัปดาห์ ยาโกดาแถลงข่าวว่ากลุ่มต่อต้านแห่งเลนินกราดที่มีซีโนเวียฟและคาเมเนฟเป็นผู้นำอยู่เบื้องหลังการลอบสังหาร อย่างไรก็ตาม ในการพิจารณาคดีแห่งมอสโก (Moscow Trial) หรือคดีกลุ่มก่อการร้ายตรอตสกี-ซีโนเวียฟ (Trotskyite-Zinovievist Terrorist Group) ใน ค.ศ. ๑๙๓๖ ยาโกดาไม่อาจทำให้สาธารณชนทั้งในและนอกประเทศเชื่ออย่างสนิทใจว่าทั้งซีโนเวียฟและคาเมเนฟเป็นผู้บงการและหลักฐานเท็จที่เยจอฟทำขึ้นก็ไม่อาจโยงจำเลยเข้ากับการจารกรรมข้อมูลของหน่วยตำรวจลับได้ชัดเจนสตาลินขุ่นเคืองกับเรื่องดังกล่าวมาก และเห็นว่ายาโกดาขาดประสิทธิภาพในการปฏิบัติงาน เขาจึงปลดยาโกดาใน ค.ศ. ๑๙๓๖ และแต่งตั้งเยจอฟเป็นรัฐมนตรีว่าการกระทรวงมหาดไทยส่วนยาโกดาถูกย้ายไปดำรงตำแหน่งรัฐมนตรีว่าการกระทรวงไปรษณีย์และการคมนาคมสื่อสาร

 การปลดยาโกดาซึ่งเป็นสหายสนิทคนหนึ่งของสตาลินเป็นผลจากเขาดำเนินการไม่เด็ดขาดเกี่ยวกับการกวาดล้างศัตรูของพรรคและประชาชน และล้มเหลวที่จะสร้างหลักฐานเท็จใส่ร้ายคาเมเนฟว่ามีส่วนเกี่ยวข้องกับหน่วยตำรวจลับตามที่สตาลินต้องการ อย่างไรก็ตามในเดือนมีนาคม ค.ศ. ๑๙๓๗ สตาลินสั่งจับกุมยาโกดาเพราะเยจอฟกล่าวหาว่าเขาลักลอบขนเพชร ฉ้อฉลทรัพย์สินพรรค และเป็นจารชนให้เยอรมนีตั้งแต่เขาเข้าเป็นสมาชิกพรรคบอลเชวิคใน ค.ศ. ๑๙๐๗ เยจอฟยังสร้างหลักฐานเท็จว่ายาโกดาวางแผนสังหารเขาและสตาลิน ในการตรวจค้นอาคารชุด ๒ แห่งในกรุงมอสโกและบ้านพักในชนบทของยาโกดา มีการพบภาพอนาจารกว่า ๘๐๐ ภาพ ภาพยนตร์ปลุกใจ ๑๑ เรื่องและอุปกรณ์ทางเพศจำนวนมาก รวมทั้งกระสุน ๒ ลูก ที่สังหารซีโนเวียฟและคาเมเนฟ ต่อมาเยจอฟยึดอาคารชุดในมอสโกเป็นของเขา ข้อหาคอร์รัปชันของยาโกดามีหลักฐานชัดเจนทั้งก่อนหน้านั้นยาโกดาคุยโอ้อวดผู้คนที่ใกล้ชิดว่าเขาใช้เงินกว่า ๔ ล้านรูเบิลตกแต่งบ้านพักและสวนในบ้านชนบทซึ่งมีกล้วยไม้และกุหลาบกว่า ๒,๐๐๐ ต้น ยาโกดาถูกพิจารณาคดีในเดือนมีนาคม ค.ศ. ๑๙๓๘ พบว่ามีความผิดในทุกข้อหา เขาถูกประหารชีวิตด้วยการยิงเป้าในวันที่ ๑๕ มีนาคม ค.ศ. ๑๙๓๘ ขณะอายุ ๔๖ ปีก่อนเขาถูกประหารเยจอฟสั่งให้ทหารยามถอดเสื้อผ้าเขาออกหมดแล้วโบยตีด้วยแส้เพื่อหยามเกียรติเขา

 ทันทีที่เยจอฟดำรงตำแหน่งรัฐมนตรีว่าการกระทรวงมหาดไทย เขาเร่งดำเนินการจับกุมกวาดล้างศัตรูทางการเมืองของสตาลินทั้งฝ่ายพลเรือน ทหารและสมาชิกพรรค เขาควบคุมการกวาดล้างครั้งใหญ่ระหว่าง ค.ศ. ๑๙๓๗–๑๙๓๘ ประมาณว่ามีผู้ถูกสังหารกว่า ๖๘๐,๐๐๐ คน และจำนวนกว่าล้านคนถูกส่งไปค่ายกักกันแรงงาน ทั้งมีการขยายพื้นที่ค่ายกักกันแรงงานเป็น ๓ เท่า ภายในช่วงเวลา ๒ ปีเยจอฟยังสั่งให้มีการพิจารณาคดีจอมพล มีฮาอิล ตูฮาเชฟสกี (Mikhail Tukhachevsky)* ใหม่ ซึ่งยาโกดาเคยสอบสวนและไม่ได้ตัดสินโทษโดยอ้างว่าหลักฐานไม่เพียงพอ ตูฮาเชฟสกีถูกทรมานและถูกบีบบังคับให้ยอมรับสารภาพว่าเขาเป็นจารชนเยอรมันและคบคิดกับนีโคไล บูฮาริน (Nikolai Bukharin)* วางแผนโค่นอำนาจสตาลิน เขาถูกตัดสินยิงเป้าพร้อมกับนายทหารคนอื่น ๆ ใน ค.ศ. ๑๙๓๗ แกนนำพรรคคอมมิวนิสต์คนสำคัญคือยูรี เปียตาคอฟ (Yuri Piatakov) คาร์ล ราเดค (Karl Radek)* และกรีกอรี โซคอลนิคอฟ (Grigori Sokolnikov) รัฐมนตรีว่าการกระทรวงการคลังและสมาชิกพรรคคนอื่น ๆ รวม ๑๗ คน ถูกจับด้วยข้อหาร่วมกันจัดตั้งศูนย์ตรอตสกีต่อต้านโซเวียต (Anti-Soviet Trotskyist Center) และเป็นจารชนให้เยอรมนีกับญี่ปุ่น ในจำนวนนี้ ๑๓ คนถูกตัดสินประหาร ๔ คนถูกส่งไปค่ายกักกันแรงงานแต่ต่อมาก็ถูกสังหาร ในการไต่สวนจำเลยให้การพาดพิงถึงกลุ่มสมาชิกปีกขวาซึ่งนำไปสู่การจับกุมอีกระลอกใหญ่ สตาลินพอใจผลงานของเยจอฟมากและแต่งตั้งเขาเป็นผู้อำนวยการหน่วยตำรวจลับ ในช่วงการกวาดล้างเยจอฟประสานการดำเนินงานอย่างใกล้ชิดกับสตาลิน และเข้าพบสตาลินโดยเฉลี่ยวันเว้นวัน สตาลินเป็นคนออกคำสั่งทุกขั้นตอนเพื่อให้เยจอฟดำเนินการไม่ผิดพลาด โดยเฉพาะกับผู้ถูกกล่าวหาคนสำคัญ ๆ นับจากการเตรียมหลักฐานวิธีการไต่สวน และอื่น ๆ ช่วงสมัยการกวาดล้างใหญ่ทั่วประเทศจึงเรียกชื่อว่า สมัยเยจอฟหรือเยจอฟชีนา

 เยจอฟก้าวสู่จุดสูงสุดของหน้าที่การงานในเดือนตุลาคม ค.ศ. ๑๙๓๗ เมื่อเขาได้รับเลือกเป็นสมาชิกโปลิตบูโร ในปีเดียวกันนั้นพรรคคอมมิวนิสต์โซเวียตจัดงานเลี้ยงฉลองใหญ่ในวาระครบรอบ ๒๐ ปีของการจัดตั้งกระทรวงมหาดไทยเมื่อวันที่ ๒๐ ธันวาคม ที่โรงละครบอลชอย (Bolshoi) มีการตกแต่งประดับธงพรรคขนาดใหญ่คู่กับภาพขนาดมหึมาของสตาลินและเยจอฟคนละด้าน บนเวทีเต็มไปด้วยดอกไม้และภาพของเยจอฟเคียงข้างกับภาพสตาลิน แม้เยจอฟจะกล่าวสุนทรพจน์ที่มีเนื้อความตอนหนึ่งว่า เขาเรียนรู้การทำงานจากสหายสตาลินและยังคงต้องเรียนรู้จากท่านผู้นำอีกยาวนาน แต่เขาก็ตระหนักว่าความเป็นบุคคลที่ทุกคนชื่นชมยกย่องนั้นอาจไม่เป็นผลดีต่อตัวเขา เพราะเป็นที่รู้กันทั่วไปว่าสตาลินไม่ชอบให้ใครเด่นเกินเขาและมักหวาดระแวงว่าบุคคลที่สาธารณชนนิยมยกย่องเป็นคู่แข่งของเขา ในงานคืนวันนั้นสตาลินเงียบเฉยและไม่แสดงอารมณ์ใด ๆ ทั้งสิ้น ต่อมาในต้นเดือนเมษายน ค.ศ. ๑๙๓๘ เยจอฟได้รับแต่งตั้งเป็นรัฐมนตรีว่าการขนส่งทางน้ำ (People’s Commissar for Water Transport) อีกตำแหน่งหนึ่ง ซึ่งทำให้เขาหมดบทบาทจากการควบคุมนโยบายการกวาดล้างอีก ๓ เดือนต่อมา สตาลินแต่งตั้งลัฟเรนตี ปัฟโลวิช เบเรีย (Lavrenty Pavlovich Beria)* เลขาธิการพรรคคอมมิวนิสต์โซเวียตภูมิภาคทรานส์คอเคเซีย (Transcaucasia) เป็นรัฐมนตรีช่วยว่าการกระทรวงมหาดไทยและรองหัวหน้าตำรวจลับ

 ในช่วงที่เยจอฟมีอำนาจ ในต้น ค.ศ. ๑๙๓๘ เขาเคยคิดกำจัดเบเรียซึ่งเป็นเลขาธิการพรรคคอมมิวนิสต์โซเวียตจอร์เจีย แต่เบเรียรู้ตัวก่อนและหนีไปขอพบสตาลินเป็นการส่วนตัว โดยยืนยันความจงรักภักดีของเขาต่อสตาลิน และการมีผลงานโดดเด่นในช่วงบริหารจอร์เจียและทรานส์คอเคเซียทั้งขอให้สตาลินไว้ชีวิตเขา ดังนั้นเมื่อเบเรียได้เป็นรัฐมนตรีว่าการกระทรวงมหาดไทย เขาจึงเริ่มลิดรอนอำนาจของเยจอฟและโยกย้ายคนที่ใกล้ชิดเยจอฟไปดำรงตำแหน่งที่ไร้ความสำคัญโดยสตาลินก็เห็นชอบ อำนาจและอิทธิพลของเบเรียที่มีมากขึ้นทำให้เยจอฟหวาดวิตกและหันไปเสพสุราและหาความสุขทางเพศเพื่อคลายทุกข์จนทำงานไม่ได้ เขายังขอหย่าจากภรรยาโดยเตือนเธอถึงภัยที่กำลังคุกคามชีวิตครอบครัวแต่เธอปฏิเสธอย่างไรก็ตามเยฟเกเนียภรรยาเยจอฟซึ่งไม่อาจทนสภาวะกดดันทางสังคมและการเมืองได้ฆ่าตัวตายด้วยการกินยานอนหลับเมื่อวันที่ ๑๙ พฤศจิกายน ค.ศ. ๑๙๓๘ ในท้ายที่สุดเยจอฟขอลาออกจากตำแหน่งรัฐมนตรีว่าการกระทรวงมหาดไทยเมื่อวันที่ ๒๕ พฤศจิกายนในช่วงเวลาเดียวกัน เบเรียก็กวาดล้างพลพรรคของเยจอฟทั้งหมด สตาลินยังสนับสนุนเบเรียให้ประณามโจมตีเยจอฟในที่ประชุมประจำปีของสภาเปรซิเดียมสูงสุดแห่งโซเวียต (Presidium of the Supreme Soviet) ในต้นเดือนมีนาคม ค.ศ. ๑๙๓๙ ซึ่งมีผลให้เขาถูกถอดถอนจากตำแหน่งต่าง ๆ ในพรรคคอมมิวนิสต์โซเวียต ยกเว้นตำแหน่งรัฐมนตรีว่าการขนส่งทางน้ำเขาอยู่ในตำแหน่งดังกล่าวจนถึงวันที่ ๙ เมษายน ค.ศ. ๑๙๓๙ อย่างไรก็ตาม ตำแหน่งดังกล่าวก็ถูกยกเลิกในวันนั้น และมีการตั้งตำแหน่งใหม่เป็นรัฐมนตรีว่าการกองเรือทางแม่น้ำ (People’s Commissariat of the River Fleet) และรัฐมนตรีว่าการกองเรือทางทะเล (People’s Commissariat of the Sea Fleet)

 ในวันที่ ๑๐ เมษายน เยจอฟถูกจับกุมและคุมขังที่คุกซูฮานอฟกา (Sukhanovka) การจับกุมเขาเป็นความลับและไม่เป็นที่รับรู้ต่อสาธารณชนและในหมู่เจ้าหน้าที่ตำรวจลับ เขาถูกทรมานและไต่สวนให้ยอมรับผิดในข้อหาเป็นจารชน กบฏ และผู้ก่อความเสียหายอย่างร้ายแรงในการจับกุมกวาดล้าง “ศัตรูของประชาชน” โดยเฉพาะเจ้าหน้าที่เชกา ๑๔,๐๐๐ คน เยจอฟปฏิเสธเกือบทุกข้อกล่าวหายกเว้นการกวาดล้างเจ้าหน้าที่เชกาซึ่งเขาอ้างว่าเป็นปฏิบัติการเพื่อปกป้องพรรคและรัฐโซเวียต เขาพร่ำยืนกรานความจงรักภักดีต่อสตาลินและพร้อมสละชีพเพื่อสตาลินต่อมาในวันที่ ๒ กุมภาพันธ์ ค.ศ. ๑๙๔๐ ศาลทหารพิจารณาคดีเยจอฟโดยไม่เปิดเผยและพิพากษาว่าเขามีความผิดทุกข้อหาและถูกตัดสินประหารชีวิต ทันทีที่ได้ฟังคำตัดสิน เยจอฟสติแตกและเป็นลมล้มพับไปกับพื้นจนยามต้องประคองเขากลับไปห้องขัง เขายื่นเรื่องขออุทธรณ์ทันที แต่ล้มเหลว ก่อนถูกประหารเบเรียสั่งให้เปลื้องผ้าเขาและโบยตีเหมือนกับที่เยจอฟเคยทำกับยาโกดาเมื่อ ๒ ปีก่อน จากนั้นเขาถูกลากไปห้องประหารในสภาพที่ยังคงมีสติครึ่ง ๆ กลาง ๆ คร่ำครวญและร่ำไห้ เยจอฟถูกยิงทิ้งที่ห้องใต้ถุนอาคารที่ทำงานของเคจีบีเมื่อวันที่ ๔ กุมภาพันธ์ ค.ศ. ๑๙๔๐ รวมอายุ ๔๕ ปี

 ก่อนเยจอฟถูกประหารไม่นานนัก สตาลินยกเลิกนโยบายการกวาดล้างและอ้างว่าเยจอฟเป็นผู้รับผิดชอบเพียงคนเดียวในการกวาดล้างครั้งใหญ่ รัฐบาลโซเวียตยังปกปิดข่าวเรื่องการประหารชีวิตเยจอฟจนถึงต้นทศวรรษ ๑๙๕๐ ต่อมาในสมัยประธานาธิบดีมีฮาอิล กอร์บาชอฟ (Mikhail Gorbachev)* นาตาชาบุตรสาวบุญธรรมของเยจอฟขอให้มีการกู้เกียรติทางสังคมของเยจอฟคืน แต่ศาลทหารโซเวียตสูงสุดปฏิเสธด้วยเหตุผลว่านโยบายและการดำเนินงานของเยจอฟในขณะดำรงตำแหน่งรัฐมนตรีว่าการกระทรวงมหาดไทยมีผลกระทบร้ายแรงต่อชื่อเสียงและเกียรติภูมิของประเทศ จึงไม่อาจคืนเกียรติและสถานภาพเดิมทางสังคมให้ได้.