關鍵路徑法（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）逐漸成為工期延誤索賠中必須的做法，並逐漸形成了很多專門的分析方法，甚至有很多人專業從事工期延誤分析的工作。