蘇臘馬都大橋連同引橋和連線道路全長18.5公里，其中跨越海峽部分長5438米，雙向四車道，主橋跨度434米，主塔高140.62米。橋樑造價1.958億美元。
該橋是中華人民共和國政府向印度尼西亞提供的援建項目之一。2001年，中國總理朱鎔基在訪問印度尼西亞時同印尼總統梅加瓦蒂會談時，承諾中國將參與印尼橋樑項目建設。後在多次互相考察後，中國和印尼方面達成協定，準備在巴厘島和爪哇島之間的巴厘海峽上架設大橋。
2002年底，巴厘島遭受恐怖爆炸襲擊，海峽大橋項目受此影響被取消。中國和印尼兩國轉而研討在馬都拉海峽上架設大橋的可能性。2004年，兩國達成協定，中國向印度尼西亞提供4億美元的優惠貸款作為大橋建設資金，中國路橋（集團）總公司和中國港灣建設總公司承建大橋。由於受到2004年印度洋海嘯的影響，工程在2005年11月19日方才正式開工，計畫於2008年年底建成，直到2009年6月10日正式開通。
