Sejarah Tambak Johor bermula pada tahun 1909 apabila landasan keretapi dari Singapura ke Johor Bahru siap dibina. Pada masa itu, perhubungan ke Singapura, yang merupakan Ibu Pejabat British di Asia Tenggara, hanya dengan menggunakan feri.

Tambak Johor direka oleh Messr Coode, Fizmaurice, Wilson dan Mitchell dari Westminster, Britain dan dibina oleh Topham, Jones & Railton Ltd dari London. Pada mulanya di tahun 1909, tambak ini cuma mengandungi sebatang landasan dari stesen kereta api Johor Bahru ke Singapura. Pembinaan jalan raya bermula pada tahun 1919 dan disiapkan pada tahun 1924 selepas empat tahun. Tambak Johor dimusnahkan oleh pihak British pada tahun 1942 semasa Perang Dunia II, untuk menghalang tentera Jepun daripada menjajah Singapura. Bagaimanapun, Tambak Johor dibina semula setelah Jepun menawan Singapura.

Tambak ini telah menjadi sumber perbalahan sejak perpisahan Singapura daripada Persekutuan Malaysia. Air yang bertakung disebabkan tambak ini telah menimbulkan rasa bimbang terhadap kesihatan di Johor. Malaysia telah mencadangkan penggantian tambak kepada jambatan semenjak awal tahun 2000-an untuk membolehkan air mengalir tetapi cadangan itu ditolak oleh Singapura. Oleh sebab itu, Malaysia bercadang meneruskan projek penggantian melalui apa yang telah digelarkan sebagai "jambatan separuh yang bengkok" (crooked half bridge). Dengan tingginya 25 meter dari aras laut, cadangan jambatan di sebelah Malaysia akan menurun untuk menyambungkan dengan tambak di sebelah Singapura. Landasan pula akan disempurnakan dengan jambatan ayunan (swing bridge). Projek itu merupakan sebahagian Projek Gerbang Selatan Bersepadu.

Sebahagian penganalisis berpendapat bahawa penggantian tambak kepada jambatan akan mewujudkan sebuah sistem pelabuhan yang menyeluruh untuk mengaitkan Pelabuhan Johor dan Pelabuhan Tanjung Pelepas. Oleh sebab-sebab yang sama, Singapura enggan bersetuju sebab penggantian tersebut akan mengancam kegiatan-kegiatan Pelabuhan Singapura.

Disebabkan kesesakan jalan raya yang teruk, laluan kedua yang dikenali sebagai Laluan Kedua Malaysia-Singapura disiapkan pada Oktober 1997. Sepanjang 1,920 meter, jambatan dua tingkat ini mengandungi jalan duaan berlorong tiga yang mengaitkan Kampung Ladang di Tanjung Kupang, Johor dengan Jalan Ahmad Ibrahim di Tuas, Singapura.

Kemarahan antara bekas pemimpin dari kedua-dua negara telahpun mereda dengan kepemimpinan yang baru, iaitu Abdullah Badawi sebagai Perdana Menteri Malaysia menggantikan Mahathir Mohamad dan Lee Hsien Loong di Singapura menggantikan Goh Chok Tong. Kedua-dua pihak telah menjalin semula perhubungan mereka dan membuat perundingan yang baharu.