From Kagoshima, it travels southwest along the first island chain that divides the Pacific Ocean from the East China Sea.

[5] Heading south by ferry, the highway resumes its land route in Nishinoomote on the northern end of Tanegashima.

Unlike the previous maritime section, no ferry carries the highway from Shimama to its next land segment on Amami Ōshima.

Upon reaching the island's southern coast, the highway curves to the southwest, heading towards the Setouchi's central district on the southwestern end of Amami Ōshima.

[4] The highway's final land segment starts near the Port of Oku in Kunigami at the northern tip of Okinawa Island.

It then meets National Route 505, and proceeds to the south, leaving the coast and crossing the bottom of the Motobu Peninsula.

The highway curves to the southwest after leaving Chatan and entering the city of Ginowan, home to the Marine Corps Air Station Futenma.

[4][3] The precursor to what would eventually become National Route 58 on Okinawa was originally established in the 15th century during the reign of Shō Kinpuku, ruler of the Ryukyu Kingdom.

The highway functioned as the island's main road during World War II and the subsequent US administration of the region.

The highway was mainly developed as a high-speed logistics route for the US military that could carry vehicles weighing up to 35 tons.

[10][7] After the return of the Ryukyu Islands from the United States to Japan on 15 May 1972, the aforementioned highways were all re-designated as a part of National Route 58.

After the 730 switch, Okinawa joined the rest of Japan in driving on the left in accordance to the Vienna Convention on Road Traffic.