关键路径法（CPM）最早出现于1956年，当时美国杜邦（Du Pont）公司拥有一台UNⅣAC 1 计算机，他们使用这台计算机进行他们公司几乎所有的数据处理工作，但是仍然还有大量的剩余时间，杜邦（Du Pont）公司的管理层开始研究计算机在其它方面使用的可能性，因为当时电脑的费用是非常高昂的，他们考虑工程计划可能是应用电脑的一个方向。他们联系了雷明顿兰德（Remington Rand）公司的Macuchy 博士，帮他们解决计算机使用的问题，后者派出了年轻的数学家James E. Kelly去协助杜邦（Du Pont）公司解决问题，杜邦公司方面的负责人是Morgan Walker。
他们要解决的问题是在工程项目中工期和费用之间的关系，他们研究的是如何能够采取正确的措施，在减少工期的情况下能尽可能少的增加费用。1957年5月7日，在特拉华州内瓦克召开的一个会议正式确定开始新计划技术的开发。Kelly借用了线性规划的概念来解决项目计划自动计算的问题，简单的说就是确定了每个活动的工期和活动间的逻辑关系，输入电脑后就能自动计算项目的工期，为了电脑的计算，Kelly在活动间使用了i，j这样的节点来表示活动间的前后逻辑关系。
当时遇到的一个问题是，杜邦公司的管理层并不理解Kelly所使用的方法，为了让其他人能够理解所使用方法的原理，Kelly就绘制了图形来解释电脑所作的工作，图形以箭线表示活动，以节点表示活动间的逻辑关系，这就是最早的箭线图（ADM）。
前面提到过，Kelly和Walker最初研究的目的是为了解决项目中工期和费用之间关系的问题，所以在Kelly和Walker最初提出的方法中，也包括费用的计划方法，其做法是，在每个活动上加载其相应的费用，从而得到整个项目的费用，就能分析与进度相关的费用问题，这种做法与现用的方法没有太大差别。但在当时的情况下，项目收集费用并分解到各个活动上存在较大困难。所以，在之后的很长时期内，关键路径法主要还是用于进度的计划和控制方面。Kelly和Walker还提出了资源加载和分配的方法，当然也存在和费用分析一样的问题。 尽管存在这些问题，在1957年7月24日，他们已经做了一个简化的例子，称为”George Fischer Works”，这个计划包括了61条活动，其中有8个时间限制和16条虚工作。在刚开发出这种方法时，他们将这种方法称为Kelly-Walker法，而计划中的关键线路，他们称之为主链路（Main chain）。
根据Kelly和Walker的论文和其它相关书籍的记载，当时他们一共进行了三个试验对Kelly-Walker法进行检验。第一个试验是在1957年12月份，杜邦公司成立了一个测试小组对这种新的计划方法测试，有一个传统的计划组与他们同时独立对一个价值1000万美元的化学设备项目进行计划。这个测试小组的成员没有参与Kelly-Walker法的开发，但是在开始测试之前，他们接受40个小时的培训。此项目的计划从初步设计的完成开始，在编制计划时，他们首先将整个项目分解成一些较小的工作包，然后再将这些工作包最终分解成为活动，项目共有800条活动，其中包括400条施工活动，150条采购和设计活动。根据记载，在此项目中显示出的Kelly-Walker法的最大优势在于，此项目在实施中出现了较大的变更，相对于传统计划方法，使用Kelly-Walker法更容易更新计划，其工作量仅有最初建立计划的10%，另外，在设计信息只有30%的情况下，能够比较准确的预测劳动力，还有就是能够比较准确的识别关键的采购工作。1958年，他们进行了第二次试验，此试验所针对的是一个价值2000万美元的化学设备项目，根据Kelly和Walker在1959年发表的论文，此次试验显示的最主要的优点是能够比较容易的包含设计部分的计划。
不过现在人们最常提及的一个试验是他们随后进行的维护设备的试验，在此项目中，他们使用Kelly-Walker法进行分析和计划，使得设备维护时间减少了25%。 1959年，Kelly和Walker共同发表了”Critical Path Planning and Scheduling” 论文，在这篇长达25页的论文中，Kelly和Walker不仅阐述了关键路径法的基本原理，还提出了资源分配与平衡，费用计划的方法。我们今天所使用的方法的原理，与Kelly和Walker在论文中提出的方法，并没有原则上的不同。
不过随后关键路径法的发展并不是很顺利，杜邦公司开发此项技术的领导层更换之后，不再使用这项技术，而雷明顿兰德公司也认为这项技术没有太大前途。
对于关键路径法的发展起到重要作用的是Mauchly博士和Kelly随后成立的Mauchly合伙公司。在60年代初期，在Kelly的带领下，此公司进行了大量的关键路径法的培训和推广工作。
与此同时，另外一个对关键路径法（CPM）的发展起到重要作用的是美国海军北极星计划开发的计划评审技术（PERT）。在1955年11月17日，美国海军北极星计划成立了一个特别项目管理办公室（SPO），管理其Fleet Ballistic Missile计划，负责人是Admiral Raborn。在1956年和1957年期间，他们研究了各种已经存在的项目管理技术，在大约1957年秋季的时候，他们接触到了杜邦公司开发的计划管理技术，这对他们开发PERT起到了重要的作用。1958年1月份，SPO研究了在计算机上实现计划和控制的可行性，1958年1月27日，SPO正式成立了一个小组开发PERT技术，在大约一年以后，PERT技术成为一种可操作性的技术，计划评审技术（PERT）和关键路径法（CPM）基本上一样，唯一的区别是计划评审技术的每个活动的工期不是确定的，而是包括了悲观值，乐观值和最有可能值三个值。比较有趣的是，1959年，北极星计划的这个特别项目管理办公室（SPO）开了一个招待会，介绍他们的这种新技术，并希望参会者能给出更多的意见，Kelly和Walker在被邀请之列，在会上，他们发现SPO开发的PERT和他们的Kelly-Walker法原理上完全一样，而SPO所说的关键线路（Critical Path），就是他们的Kelly-Walker法中的主链路（Main Chain）。回去之后，他们决定将它们的方法的名称改为关键路径法（Critical Path Method）。 在60年代初期，PERT的发展比较迅速，据统计，到1964年，关于PERT的参考书目和论文达到了1000多种。到1961年，各种基于PERT的类似的方法出现，如PERT/Cost,PERT-RAMPS（Resource Allocation & Multi-Project Schedule），MAPS，SCANS，TOPS，PEP，TRACE，LESS和PAR等。其中PEP法是将甘特图的活动赋以逻辑关系，这是计划软件一般采用的一种图形输出方法。1962年的时候，时任美国国防部长MacNamara在起草一项法令时，指出计划评审法和关键路径法同时并存的局面容易引起混淆，以后国防部的所有部门一律使用计划评审法（PERT），这在当时对于关键路径法的提倡者是一个重大打击，不过在随后的发展中，关键路径法（CPM）逐渐占了优势，真正使用计划评审法的其实已经很少。而且即使是在当时，很多所谓的计划评审法（PERT），其实质其实是关键路径法（CPM）。如美国航空局（NASA）当时使用的NASA-PERT，实际就是关键路径法（CPM）。
无论是关键路径法（CPM）还是计划评审法（PERT），最初使用的表示方法都是箭线法（ADM），在之后很长的一段时间箭线法（ADM）都是人们主要使用的方法，直到70年代以后，前导图（PDM）才开始逐渐流行起来，但是箭线法（ADM）仍然使用极为广泛。在90年代以后，美国Primavera公司开发出其Windows版本的计划管理软件时，只采用前导图（PDM）作为其计算平台，从根本上改变了这一局面，从此以后，前导图（PDM）成了人们主要使用的方法，而箭线图（ADM）则很少使用。 在早期对于前导图（PDM）的发展起到重要作用的是美国斯坦福大学的John W. Fondahl,他是60年代初期的非计算机关键路径法的权威，1961年他发表了一篇题为”A Non-computer Approach to Critical Path Methods for the Construction Industry”，在这篇论文中，他阐述了前导图系统，并把它作为一种效率比较高的手工绘制关键路径法的方法，因为当时使用计算机运行CPM是非常昂贵的。Fondahl从1958年开始作为斯坦福大学的成员，受美国海军委托为其研究提高生产效率的方法。其中最主要的成果就是这份论文，这份论文当时一共出售了20000份。
在这份论文中，根据习惯使用的流程图方法，Fondahl提出了以节点表示活动以连接线表示活动间的逻辑关系。论文论述了流程图的简易性和使用手算在较少的人力投入下采用关键路径法的可能性，同时论文也论述了费用工期互为反比的问题。斯坦福大学之后继续研究了前导图（PDM）的手工进度更新的问题，并在1964年发表了相关的技术报告。
虽然Fondahl博士极力强调他提出的方法是为了手工计算关键路径法，但是H.B Zachry公司在1962年开始研究将前导图法用于计算机上，1963年3月他们与IBM公司联合进行该项研究，之后形成了IBM的计划软件，名为”Project Control System（PCS）”。该系统还是第一个在计划中引入时间间隔（LAG）的软件。虽然前导图法最初被应用于大型机，但是随后被广泛应用于小型机和个人电脑上的软件，这一趋势使得前导图（PDM）逐渐成为主要使用的方法，在国外前导图（PDM）基本已经成为唯一在使用的方法，而箭线图（ADM）只有在教学和培训中还有时用到。而发展势头曾一度压过关键路径法（CPM）的计划评审技术（PERT），正在使用的已经很少了。
在美国发展出关键路径法（CPM）和计划评审技术（PERT）的同时，其它一些国家如欧洲和英国等，也曾经开发出一些类似的项目管理技术，但是关于这些技术的记载已经很少。
关键路径法（CPM）最初被开发是用于项目管理，不过，在发展过程中，它逐渐在工程项目的合同索赔和纠纷解决上起到重要作用。最早在诉讼中涉及到要求使用关键路径法（CPM）是1972（Appeal of Minmar Builders,Inc,GSBCA No. 3430,72-2 BOA）年，在此案例中，法庭由于承包商没有使用关键路径法（CPM）而拒绝了承包商的索赔，因为其使用的横道图不能显示具体的活动是否在关键线路上，从而无法判断活动耽误对于整体的影响。之后，关键路径法（CPM）逐渐成为工期延误索赔中必须的做法，并逐渐形成了很多专门的分析方法，甚至有很多人专业从事工期延误分析的工作。
