In the year after the start of the shogun government in Edo (1603), five major avenues were designated with Nihon-bashi Bridge as the starting point. These were Tokaido Avenue, Nakasendo Avenue, Nikko-kaido Avenue, Oshu-kaido Avenue and Koshu-kaido Avenue. Inns were placed along each avenue, and the inns were obliged to provide horse messenger services.
Koshu-kaido Avenue was the main road from Nihon-bashi Bridge to Kofu, and from Kofu connected to Shimo-Suwa via the Nakasendo Avenue. Nihon-bashi Bridge was a long way from the first inn area—Takaido—on the Koshu-kaido Avenue, and travelers had a difficult time making the trip. For this reason, upon the request of Lord Takamatsu Kiroku , authorization was received to place an inn in an area midway. Since the inn was placed on the property of Lord Naito, who returned this land to the Shogun government, and since the inn was new, the area was called Naito-Shinjuku (Naito new inn), thus marking the origin of the name Shinjuku for the area.

On March 15, 1947, the three areas of former Yotsuya, Ushigome, and Yodobashi cities merged to create Shinjuku City. The name Shinjuku was used not only because of its historical significance, but also because Shinjuku Gyoen National Garden and Shinjuku Station were well known across Japan.