“我们希望派你去乌克兰，领导那里的党组织。看来，科西奥尔（Kossior）可能没法领导那里的工作。我们将调他到莫斯科担任人民委员会第一副主席和中央委员会里一个委员会的主席。”
这就是1937年底斯大林宣布赫鲁晓夫晋升时的情景。下面是赫鲁晓夫自己当时的反应：
我是不愿意接受这一任命的，其理由有三：第一，我喜欢科西奥尔，我感到取代他的地位是于心不安的。1929年，当他接替卡冈诺维奇担任乌克兰中央委员会第一书记时，我就认识他了。就是那一年，我申请进入工业学院，也就是科西奥尔批准了我的申请。第二，我怀疑自己是否有足够的经验或资格去代替科西奥尔的地位；我认为这顶乌克兰第一书记的帽子对于我的头来说是太大了。第三，我脑子里还考虑到了民族问题。不错，我曾在乌克兰工作过，我一直同乌克兰共产党人和非共产党人相处得很好。然而，作为一个俄罗斯人，置身于乌克兰人之中，我仍会感到一些尴尬。虽然我懂得乌克兰语言，但我从来没有达到能够用它来发表演说的程度。我将所有这些向斯大林作了解释，并对他说，我担心乌克兰，特别是知识分子，可能会对我很冷淡。我对他说：“派我这样一个俄罗斯人去乌克兰没有什么意义。”
“科西奥尔不是俄罗斯人，对吧？他是波兰人。为什么一个俄罗斯人同乌克兰人相处会比一个波兰人更感困难呢？”
“科西奥尔可能是波兰人，”我承认说：“但是他能用乌克兰语发表演讲。再者，科西奥尔比我有更多的经验。”
“不要再说了。就你去乌克兰。”
“那很好。我将尽我所能开展工作，使乌克兰党组织重新健全起来，不辜负你对我的信任。”我仍在担忧我是否应付得了这个任务，但我不能否认，中央委员会如此信任我，给我这么高的职位让我感到很高兴。
赫鲁晓夫不仅被赋予乌克兰的最高职位（虽然只是暂时“代理”），而且斯大林坚持要求他同时主管基辅市委与地区党委的工作。
我对他说我不可能同时担任这许多职务，但他的态度很坚决。
他说：“你可以胜任。只要你到那里，你可以选用一些你中意的人帮助你。”
赫鲁晓夫雄心勃勃，有机会在他工作和生活多年的地方成为一方主管，他肯定会乐不可支。但是他内心对做不好工作的担心也是真实的，他向斯大林不止一次地强调过这一点。此外，他还有一点担心，就是他有可能成为在大清洗中人头落地的乌克兰领导人中的一个。
赫鲁晓夫是于1938年1月离开莫斯科前往基辅的。在其后的十年里，他经常去首都参加政治局以及其他的会议。不过只是到了1949年底他才作为新当选的中央委员会书记永远地回到了莫斯科。到那时，他已经越来越独立于斯大林并对斯大林越来越失去幻想。不过在这一时期，他仍然忠实而有效地为斯大林服务。这一时期使赫鲁晓夫发生改变的更多的是由于战争，但是他改变的进程在1941年希特勒进攻苏联前的三年在乌克兰就已经开始了。
赫鲁晓夫能获得部分的解放，能更有效率地工作，其关键是他与莫斯科之间的距离。没有一个处于斯大林势力范围的人，甚至是他委任到乌克兰的总督，能够有自主决策的权力。不过基辅离苏联权力中心的距离实在是太远了，这使得这里可以存在苏联人所谓的地方主义。赫鲁晓夫相信他比克里姆林宫更了解乌克兰。他不仅对接近斯大林得通过其周围的人感到不满，而且他也开始看透斯大林本人了。
距离让赫鲁晓夫有机会发挥他自己的风格与才能在基辅为赫鲁晓夫工作的。一位名叫瓦西里·科斯坦科（Vasily Kostenko）的共青团官员回忆说，他是“一个很特别的人”。他“知道事情的具体运作情况”。他“知道如何与人交谈。他能感觉出什么人他可以开玩笑，哪些人，像他一样，太年轻了，还不知道如何对他所开的玩笑做出反应”。他是“一个无所畏惧的人”，“一位可以担当领导的伟人”。
回到基辅后，赫鲁晓夫很快了解到了更多关于乌克兰农业集体化、饥荒以及清洗恐慌的情况。在对彼得罗夫-马林斯基地区（他1925年曾担任过该地区的党委书记）的一次视察中，他详细询问了以前与他关系不错的几位农民的情况，其中包括几位很要好的富农朋友。“他担心他们已经被‘非富农化’”，扎赫尔·格鲁赫夫（Zakhar Glukhov）回忆说，1938年他担任赫鲁晓夫从前的职位，“赫鲁晓夫是那种你可以与他坦诚交谈的人。他有一位名叫哥马利亚（Gomlia）的朋友，赫鲁晓夫和他形影不离，他很得赫鲁晓夫的器重，他可以告诉他所有发生的事情”。
当赫鲁晓夫到达基辅时，大清洗已经横扫了乌克兰的所有机构。乌克兰党组织已经大部分被破坏了，被捕的人太多了，以致乌克兰中央委员会都达不到法定的开会人数。他“十分尊敬的”斯大林诺冶金学院的几位教师被逮捕了。他曾经碰到了其中的一位教师，他“已经变得形容枯槁。‘你怎么样？’我问他。他看上去很沮丧，表情木讷。他咕哝着说不好，他被逮捕了。后来其他的人告诉我，他遭到了毒打，就这样他的健康被毁了。不久以后他就死了”。
类似这样的相遇可以帮助我们理解为什么赫鲁晓夫偶尔会向他的老朋友们承认他的疑惑及对斯大林思想的幻灭。然而主持乌克兰清洗工作的也就是这位赫鲁晓夫，在他到来后，乌克兰的清洗步伐明显加快了。光在1938年，据说就有106119人被逮捕，在1938-1940年间，被捕人数达到了165565名。根据莫洛托夫的说法，在很少有客观证据但却不乏告密者的情况下，赫鲁晓夫“作为乌克兰三驾马车中的一员将54000人送到了另外一个世界”。赫鲁晓夫的话里滴淌着毒汁，至少在为外人所知的一件事中是如此，他在一份文件上圈上“逮捕”一词，这样就决定了乌克兰共青团一位高级官员的命运。[1]
与在莫斯科时一样，对苏联制度的信念仍然激励着赫鲁晓夫。作为一块面积差不多与法国相当的领地的主人，他通过自己惯常的精力与坚定的意志将农业、工业与文化纳入他的羽翼之下，通过控制乌克兰西部地区并将它们与苏联乌克兰其他地区联系起来，通过试图改善他自己监控的大恐怖行动，当然是在严格的限制条件下并以周全的方式，让自己相信他是在为那里的人民谋福利。不过他也是在为自己的利益服务的。现在赫鲁晓夫家已经有五个孩子，加上其他一些到基辅与他们住在一起的亲戚。他们所有的人，甚至那些在莫斯科过着优裕生活的人，对他们简直不敢想象的优越条件感到很满足。赫鲁晓夫也有着对自己及其家人的担忧。执行清洗政策的他的基辅前任现在已经失去了所有的一切，甚至连他们的妻子和孩子也没有幸免。然而就在当时，不管这一切显得多么矛盾，他过得是很满足的。不再有起起落落，他已经爬上了高位，他享受着斯大林比以往更为热情的认同，他正在从自己的成功以及其他人的失败中赢得自信，包括斯大林的失败。
除了俄罗斯外，乌克兰当时是苏联最为重要的部分。然而人们怀疑乌克兰，至少在其一些公民当中，尤其是在知识界，有着民族主义的诉求，这与马克思主义的国际主义以及斯大林对极权主义控制的追求相抵触。在经历数个世纪的基辅统治后，其间根植于乌克兰的文明控制着他们自己的命运，并对东欧邻国的生活产生了巨大影响，该地区落入了外人的控制之下，首先是蒙古，然后是立陶宛、波兰和俄罗斯。从18世纪末至20世纪初，乌克兰的领土为俄罗斯与哈布斯堡王朝[2]所瓜分，大约80%的人口臣服于俄罗斯。19世纪后期，乌克兰的民族意识开始滋长，第一次世界大战中俄罗斯帝国的崩溃为乌克兰独立主义提供了一次机会。在1917年的立宪会议选举中，布尔什维克在乌克兰只得到了10%的选票（以农民为基础的社会革命党赢得了75%的选票），在1917-1920年间，各式各样的民族主义政权在乌克兰执掌过权力，不过最后取胜的还是列宁的政党。
为了保住乌克兰，也为了遵循他理论上对俄罗斯沙文主义的反对，列宁同意让有着民族主义思想的同事担任乌克兰共产党的领导人，例如像留布钦科（Lyubchenko）和格里高里·格里连科（Grigory Grinko）等，后来他们都在大清洗中被处决了。乌克兰的其他主要共产党人，例如尼古拉·斯克里普尼克（Nikolai Skrypnik）对1922年12月正式建立苏联的协议持反对意见，这一协议理论上承认乌克兰是自治区，但实际上从属于苏联共和国。在不顾乌克兰的反对建立起联盟后，斯克里普尼克和乌克兰总理瓦莱斯·丘巴尔对位于莫斯科的全联盟机构试图控制乌克兰经济生活的努力给予了抵制。
在组建苏维埃加盟共和国中未能占得上风的乌克兰“民族主义共产党人”注定是要被制裁的，但是暂时他们可以（甚至得到了莫斯科的鼓励）在文化生活中培植乌克兰化倾向。乌克兰化就是通过将共产主义披上当地语言与文化的外衣使布尔什维克在非俄罗斯地区的统治合法化的一种努力。这意味着任命乌克兰人担任党和国家的高级领导职务，将乌克兰语确立为国家机构内的官方语言，在学校里推广乌克兰语的使用，以及培育乌克兰文学、艺术与历史编撰工作。
斯大林从一开始就对乌克兰化持有疑义。于是他在1925年任命拉扎尔·卡冈诺维奇为乌克兰党委书记。到了1928年，卡冈诺维奇已经让格里连科和丘巴尔他们无法忍受了，于是他们向斯大林发出抱怨，斯大林就用科西奥尔取代了卡冈诺维奇。
具有讽刺意味的是，召回卡冈诺维奇标志着乌克兰民族主义共产主义结束的开始。1930年仍具有一定影响的非共产主义乌克兰民族主义分子成为了第二年春天审判的对象。1933年春天，当斯大林的恐怖与饥荒达到最高潮时，乌克兰的紧张气氛进一步升级。至此，就连忠实地执行斯大林可怕法令的共产党人都充满了疑惑。这也就是为什么斯大林将帕维尔·波斯蒂谢夫（Pavel Postyshev）派到基辅，授权他以乌克兰以外的忠实可靠的俄罗斯人取代乌克兰没有忠心的共产党人的原因。[3]斯克里普尼克在1933年夏天受到了共产党媒体的恶毒攻击，于7月份自杀身亡。他在知识界的支持者在随后的几次审判中被“揭露”为宣称的“乌克兰军事组织”的成员。
与莫斯科一样，乌克兰在1937年的风暴来临前有着片刻的宁静。1937年一开始，波斯蒂谢夫本人在他的支持者被驱逐出基辅党组织后也遭到了攻击。接着，斯大林反映一位名叫尼古拉延科（Nikolayenko）的女性，“一位普通的党员……一个寻常的‘小人物’”一直在揭露基辅的“托洛茨基异端分子”，但是“基辅党组织像讨厌的苍蝇似的躲避她”。莫斯科已经开始着手调查，斯大林继续说：“据反映，尼古拉延科是正确的，而基辅党组织是错误的。”[4]
1937年3月，乌克兰中央委员会解除了波斯蒂谢夫的职务，暂时由科西奥尔代理工作，领导对他已经下台的副手的攻击。留布钦科一直坚持到8月份，后来乌克兰中央委员会投票通过将他清除出党组织，并下达了对他的逮捕令。[5]就在几周前，赫鲁晓夫还用斯大林的专车带着留布钦科、科西奥尔和波斯蒂谢夫游览了莫斯科。赫鲁晓夫记得：“我们之间的关系不能再好了，甚至超出了党的同志情谊。”但是就在8月30日傍晚，留布钦科开枪杀死了他的妻子后自杀，同一天，时任人民财政委员的格里连科在莫斯科被捕。科西奥尔与他原来的基辅同事丘巴尔一起临时被任命为全联盟的代理总理，后来赫鲁晓夫取代科西奥尔成为乌克兰党委书记。后来科西奥尔于1938年4月底被捕（唯一的“宣布”就是基辅电台停止称自己为科西奥尔电台），而丘巴尔则于6月份被解除职务，流放到乌拉尔地区，后来在那里被捕。科西奥尔与丘巴尔都于1939年2月接受了审判。1939年2月26日，他们与波斯蒂谢夫一起被枪决，尽管他们已经供出自己的“大量罪行”。科西奥尔幸存的兄弟（其他两个兄弟此前已经分别自杀和被处决）也被处决，还有他的妻子叶利查维塔（Yelizaveta）。波斯蒂谢夫的大儿子也被处决，其他的孩子被流放到劳改营里，他的妻子经受了很多折磨，后来据说被枪决了。丘巴尔的妻子也被枪决了。
