Pembinaan BKE baru bermula pada Disember 1994 dan tamat pada September 1996. Hal ini demikian kerana kenderaan di Bandar Bukit Mertajam telah semakin bertambah banyak terutamanya kawasan menuju ke Butterworth. Jadi, sebuah lebuhraya kena dibuat dekat Butterwowth sampai ke Kulim, Sungai Lembu, dan Lunas.

Kadar tol BKE ini tidak dijangka naik pada masa sekarang sebab bayaran tol di BKE ini adalah tinggi.

Konsortium Lebuhraya Butterworth-Kulim (KLBK) Sdn Bhd, anak syarikat PLUS Expressway Berhad ("PLUS Expressways") telah diberikan konsesi serta kontrak membina dan mengendalikan lebih raya kembar empat lorong dengan lorong motosikal serta kemudahan berkaitan bagi lebuh raya sepanjang 16.78 km. Tempoh konsesi adalah selama 32 tahun (Jun 1994 hingga Jun 2026, termasuk 2 tahun tempoh pembinaan), di mana selepas itu lebuh raya berkenaan akan diserahkan kepada kerajaan persekutuan.