Lebuhraya Timur-Barat mula dibina pada tahun 1967. Proses pembinaannya kerap kali terganggu akibat perbuatan khianat pengganas komunis yang sering sahaja menyerang hendap pekerja binaan sepanjang Perang Insurgensi Komunis ataupun Darurat Kedua dari tahun 1967-1989, menyebabkan pembinaan lebuh raya ini memakan masa yang sangat panjang. Malah, semasa lebuh raya ini dibuka pun pihak tentera mengawal ketat lebuh raya ini dan pemandu hanya boleh menggunakan lebuh raya ini pada waktu siang sahaja dan perlu melapor diri setiap kali menggunakannya.

Sistem kawalan keselamatan yang ketat dimansuhkan setelah pihak komunis menyerah diri sepenuhnya pada tahun 1989. Sebuah tugu peringatan dibina oleh Jabatan Kerja Raya di Pulau Banding bagi menghormati para pekerja yang terkorban akibat serangan hendap komunis sepanjang pembinaan Lebuhraya Timur-Barat.