千住新橋北詰めから埼玉県界水神橋に至る区間の新設は、当時の社会情勢から政府が失業対策と救済の目的を持つ、内務省直轄の事業として着手された。道路の完成が急がれたため、工事区間を二工区に分け、三一（昭和六）年度から工事は開始された。その区間は「南足立郡梅島町小右衛門新田ヨリ同郡淵江村保木間ニ至ル延長三、三五四メートル、幅員二五メートル、同郡梅島町小右衛門新田ヨリ同郡千住町八千代町ニ至ル延長一、八五一メートル、幅員二五メートル、総延長五、一九四メートル」としている。

　千住新橋北詰めより小右衛門新田（現・環状七号線交差点）までの用地買収は、三一年から三三年にかけて、建築物等の物件の移転と共に東京府が執行し、その費用を負担した。小右衛門新田以北、埼玉県界までは、内務省が直接用地の買収を行った。

　新四号国道は、線路を変更した東武鉄道と交差するため、その交差部に内務省直轄工事で、梅島橋（陸橋）が架けられた。三二（昭和七）年から工事を開始し、三三年度に完成した橋長四三二・九m、幅員六mの鋼鈑桁及び鋼工桁橋である。

　新四号国道は三四（昭和九）年三月に完成し、二六日その区域と供用の開始が告示された。足立区内を貫く交通の大動脈となったが、地域の人々の間では、今も十三間道路(じゅうさんげんどうろ)と呼び慣らし、変更で廃止された従前の国道（陸羽街道）は、今も地域に密着し旧道と呼ばれ親しまれている。