1965年初，大連機車車輛廠、大連熱力機車研究所、大同機車廠、鐵道科學研究院等機構聯合組成新中速柴油機設計組，首先重點是研製柴油機車的動力來源——新型大功率中速柴油機。當時同類型柴油機的設計參考資料十分缺乏，設計組隻能從國內外雜誌文獻中尋找相關資訊，將國外同類型柴油機及機車的數據、圖片以及使用中情況等作為設計參考，例如蘇聯哈爾科夫運輸機械製造廠的Д70係列、法國阿爾薩斯機械製造公司的AGO 240係列、瑞士蘇爾壽公司的LVA24係列等。1965年7月，鐵道部內燃機車會戰指揮小組在青島召開會議，批準下達新中速柴油機設計任務書，主要技術指標為缸徑240毫米、行程275毫米、小時功率4000馬力、額定功率3600馬力、額定轉速為每分鍾1100轉、四衝程、16缸、渦輪增壓。1966年初，大連機車車輛廠試製成雙缸機並調試成功，雙缸機最大輸出功率突破500馬力，證明16缸機可達到4000馬力的預期目標。1965年8月，完成試製首台16缸的16V240ZJ型柴油機樣機，同年內完成新型機車的總體設計。
1969年，大連機車車輛廠對原有的設計方案進行局部修改，將之前試製的柴油機和牽引電機組樣機安裝在機車上，同年9月26日試製出首台東風4型2001號機車。但由於這台機車為“國慶獻禮”草率上馬，其零部件未經必要的試驗考核和改進，柴油機和電氣部分以及機車其它一些裝置未達到設計要求，導致整台機車的性能和質量都未能過關。此後，大連機車車輛廠針對原型車試運行中出現的問題，多次改進後最終形成了東風4B型機車。
