国鉄に代わって新線建設を行い、完成した鉄道施設を国鉄に貸し付けまたは譲渡することを目的に1964年3月23日に国と国鉄の出資で発足した。建設事業は運輸省の鉄道建設審議会の諮問に基づいて運輸大臣が指示する基本計画に従って行うこととされ、工事線62線、調査線3線の計65線が示された。1970年には整備新幹線、1972年には東京都、大阪市、名古屋市とその周辺の民営鉄道線建設事業も追加された。

工事線は地方開発線（A線）、地方幹線（B線）、主要幹線（C線）、大都市交通線（D線）、海峡連絡線（青函トンネル、E線）、整備新幹線（G線）、民鉄線（P線）の7つに区分され、完成した路線は公団が国鉄や民鉄の鉄道事業者に貸し付けた。ただし建設路線の大半を占めた地方開発線及び地方幹線（AB線）は計画段階から黒字が見込めないローカル線で、完成後は国鉄に無償貸し付けまたは譲渡されたが、国鉄の経営を圧迫するもととなった。

1980年、国鉄再建法施行にともなって運輸省は、同法の特定地方交通線基準に準じ、開業後見込まれる輸送密度が1日1km当たり4,000人未満の路線については、受け皿となる第三セクターなど国鉄以外の運営主体がない限り建設凍結することを決めた。このため鹿島線（鹿島臨海鉄道大洗鹿島線）および内山線（内子線向井原－内子間）以外の工事中AB線38線区はすべて工事が凍結された。

1998年に時限立法の期限切れによって解散した日本国有鉄道清算事業団の業務を継承し、公団内に国鉄清算事業本部を設置。償還スキームが破たんした清算事業団の国鉄長期債務は公団には引き継がれずに国の一般会計に組み込まれ、60年間の国民負担で処理されている。

2001年3月現在の職員数は約1800人だった。国の特殊法人改革の一環で2003年9月30日付で解散し、新設の独立行政法人鉄道建設・運輸施設整備支援機構に統合された。