基里尔·阿法纳西耶维奇·梅列茨科夫1897年6月7日生于俄国梁赞省扎赖斯克县纳扎利耶沃村的一个贫农家庭。7岁帮父亲耕田耙地，9岁就跟大人一样干地里所有的农活，15岁时来到莫斯科当钳工，1918年加入红军。
1918年6月，白军袭击弗拉基米尔省的穆罗姆城苏维埃，占领了该市，梅列茨科夫率领赤卫队参与了收复该市的战斗。8月底红军发动喀山战役，以夺回被捷克斯洛伐克军团和立宪委员会人民军所占据的喀山，梅列茨科夫被选入弗拉基米尔支队，担任政委，开始了他的军旅生涯。9月，省级机关命令他去总参谋部军事学院学习。
梅列茨科夫的生活经历使他没能受到系统的中等教育。然而，多少年来他一直渴望有机会能够补上这一课。所以，他非常珍惜这次的学习机会，在学院如饥似渴地学习，不断地充实自己，提高自己。
1919年5月，梅列茨科夫被派到顿河地区的第九集团军第十四师任参谋长助理。最初任务是在司令部里收集情报，标注作战地图。他认为在通信不畅的情况下，这种方式难以反映实际情况，要求自己到各部队收集情报，得到了司令斯捷平尼的批准和信任。
6月份，由于友邻部队撤退，第十四师为避免被邓尼金的军队和哥萨克骑兵合围也被迫撤退。撤退后，梅列茨科夫和所有在战斗中幸存的一年级学员一起又调回军事学院去读二年级。
1920年夏天，梅列茨科夫再次中断学习，被派往西南方面军司令部所在地哈尔科夫，见到了司令员亚历山大·叶戈罗夫，并和军事委员会委员约瑟夫·斯大林进行了长时间的谈话，随后被分配到谢苗·布琼尼指挥的骑兵集团军下属第四师任参谋长侦察助理。不久，又被派往谢苗·康斯坦丁诺维奇·铁木辛哥率领的第六师任参谋长助理，除了负责侦察也参与作战工作。
1920年8月，他参加了苏波战争，半个月后，因战斗任务转交给了西方面军又回到军事学院进修三年级课程。梅列茨科夫在回忆录中认为这段在骑兵集团军的生活对他影响颇大，“1917年夏季到1920年夏季可以作为我成为军事首长的第一个阶段”。
梅列茨科夫在总参军事学院所学的课程内容丰富，包括哲学、政治经济学、历史和军事科学等诸多课程，还常有军事首长来学院做讲座。1921年10月份他通过了学院的毕业考试，在论述“战略和战术中思想和意志的统一”的题目上得到优秀。
毕业后，梅列茨科夫被推荐到驻彼得格勒的独立训练旅任旅长，但西部战线司令图哈切夫斯基向谢尔盖·加米涅夫要求，把骑兵出身的他调往西部军区，组建白俄罗斯骑兵军司令部，随后他用了9个月时间整顿了情况十分糟糕的托木斯克骑兵师。
1923年年底，梅列茨科夫被派往高加索军区任顿河步兵第九师参谋长。他积极顺应当时目标为正规化、制度化的军事改革的要求，在补充兵员、训练新兵和加强装备方面作了很多工作。
1924年7月，他被任命为莫斯科军区动员部部长。上任后，他和组织部长戈尔巴托夫一起提出减少办事人员，增加效率的方案，得到了革命军事委员会主席米哈伊尔·伏龙芝和军区司令伏罗希洛夫的支持。
9月，他兼任军区副参谋长，在伏龙芝和伏罗希洛夫领导下参与了地方民兵制度和后勤制度正规化的改革，并试验了局部动员的效果。在此期间他还常受军事学院的委托，为学员介绍地方工作的经验，与院长帕维尔·帕夫洛维奇·列别杰夫就正规军与地方军事力量配合进行过讨论。
1925年秋，伏罗希洛夫接任去世的伏龙芝任革命军事委员会主席，巴济列维奇代理莫斯科军区司令。之后的三年，梅列茨科夫与他配合成功地完成了军区的军事改革工作，巴济列维奇的言传身教给了他很大帮助。
1928年11月，莫斯科军区新任司令员伊耶罗尼姆·彼得洛维奇·乌博列维奇到任，他担任过多个军区的司令员，并曾于1927年至1928年在德军总参高等军事学院学习。乌博列维奇强调阶级教育、训练和新式装备的重要性，组织了多次实兵演习。
乌博列维奇对演习的讲评、在提高平时训练和对坦克兵的指挥水平、建立坦克兵训练基地和需要加强空中防御的意见深深影响了梅列茨科夫。梅列茨科夫认为乌博列维奇影响了自己的一生，他在回忆录中写道：“在这以前还没有一位军事首长能像他那样使我获得那么多的教益。”
1930年，梅列茨科夫被任命为步兵第十四师师长兼政治委员，不久根据苏联和魏玛共和国签订的《苏德友好中立条约》，他被编入红军指挥官小组前往德国参谋部进行考察交流。他对德国参谋部里工作的熟练度和良好的组织印象深刻，但是也认为这样作过于墨守成规，会限制参谋人员的能动性。
回国后，梅列茨科夫被调往和德国接界的白俄罗斯军区任参谋长，重新在乌博列维奇指挥下工作。梅列茨科夫除了强调训练强度以外，还发现白俄罗斯军区交通状况不佳，一旦遇到突发事件，不同地域上的部队将无法联系，于是在修筑军队调动所用的道路和改善整个交通线路上进行了大量工作，但因财政拨款不足只完成了一部分。
1934年，梅列茨科夫在白俄罗斯军区组织了一次大规模的联合演习，次年梅列茨科夫和作战部部长马特维·扎哈罗夫、罗季翁·雅科夫列维奇·马利诺夫斯基合作编写的纵深战斗细则开始在部队中使用。
1936年10月初，西班牙佛朗哥的军队开始围攻马德里，苏联派出以别尔津为首的军事顾问团，梅列茨科夫和马利诺夫斯基、坦克兵专家德米特里·巴甫洛夫、炮兵专家尼古拉·沃罗诺夫都作为军事顾问被派往西班牙。
梅列茨科夫来到西班牙后，首先勘察了马德里城的地形，然后又到步兵部队鼓励因撤退而情绪低落的士兵，协助一步步把组织纪律性不强的西班牙共和国军队改组成正规军。他还劝说西班牙首相弗朗西斯科·卡巴列罗离开马德里，前往巴伦西亚组织抵抗。
1936年11月，佛朗哥军队开始从正面进攻马德里，梅列茨科夫一方面协助组织防御，一方面负责在阿尔瓦赛特组建国际纵队。随着国际纵队和苏联坦克群的投入战场，佛朗哥军队的进攻被击退。
1937年，佛朗哥决定以意大利远征军为主力，从马德里的东南面沿哈马拉河进攻，希望切断马德里和海港城市的联系。此时马德里防御委员会主席的军事顾问格里戈里·伊万诺维奇·库利克被调回国，梅列茨科夫接替他的职务，具体组织马德里的防御。
1937年2月，梅列茨科夫指挥了哈马拉河战役。此次战役，梅列茨科夫通过有效防御消耗了叛军力量，然后通过反击击退了叛军的进攻。3月，他又指挥了瓜达拉哈拉战役，歼灭叛军6000余人，取得了对意大利远征军的决定性胜利。回国后，梅列茨科夫获得1枚红旗勋章和1枚列宁勋章。
1940年夏季，梅列茨科夫被任命为副国防人民委员。国防人民委员是苏联元帅铁木辛哥。
当时，国际形势日益恶化。法西斯德国扩大了侵略，比利时和荷兰遭到了占领者铁蹄的践踏，法国北部也被德军占领。
为了抵御可能来自德国的进攻，苏联国防人民委员部决定在白俄罗斯军区举行军事演习。演习过程中炮兵和坦克进行了实弹射击，而步兵则实施进攻和防守训练。各步兵兵团的训练被认为是令人满意的，炮兵的训练水平及其同步兵的协同能力以及空军的训练水平都达到了标准。
1941年春季，梅列茨科夫参加了波波夫上将为司令员的列宁格勒军区的数次演习。演习中指挥人员能正确地完成所接受的任务，部队训练有素，攻防有序，他感觉十分满意。在此之后，梅列茨科夫又去基辅特别军区检查了训练情况。
5月底，军区司令部作战部部长巴格拉米扬上校向梅列茨科夫报告了令人不安的情况：无数德军集中到了苏联边境线的附近。巴格拉米扬还报告了不断增多的德军集结的具体数字。
在向莫斯科报告之前，梅列茨科夫决定再将整个情况核查一遍。他去了利沃夫，到了军区的各个集团军。各集团军司令员都提到了同样的情况。梅列茨科夫还亲自在前沿的边境哨所里观察了很长时间，亲眼看到了德国军官们异常活跃的情况。
梅列茨科夫又去了基辅和敖德萨，在敖德萨遇见了军区参谋长扎哈罗夫少将。梅列茨科夫听取了他的详细汇报，从中了解到，这边国境线上也呈现出一幅令人不安的景象。此后，梅列茨科夫同他一起去了罗马尼亚警戒线。梅列茨科夫在观察时发现，对方也有一群军人在观察他们。后来得知，这群军人就是德国军官。
梅列茨科夫此时真切地感觉到，战争已经迫在眉睫。他火速赶往莫斯科，然后同铁木辛哥一起来到斯大林那里，讲述了他看见的一切以及他的担忧。斯大林和铁木辛哥都非常注意这个汇报。听完汇报后又命令梅列茨科夫去检查一下空军的备战状况。梅列茨科夫接受任务后，立即飞往西部特别军区。