I begyndelsen af 1600-tallet anlagde Tokugawa-shogunatet et net af hovedveje med det formål at forbinde Edo - datidens navn for Tokyo - med andre vigtige byer såsom Kyoto, der dengang fungerede som landets hovedstad, idet det var her, Kejserfamilien boede, mens shogunatet derimod havde base i Edo. De fem ruter var tilsammen kendt som Gokaido, men blev hver især kaldt for Tokaido, Nakasendo, Koshu Kaido, Oshu Kaido og Nikko Kaido, og alle udsprang fra Edo, men kun to af disse havde endestation i Kyoto, hvilket var Tokaido og Nakasendo, mens Nikko Kaido førte til Nikko, Oshu Kaido førte til Shirakawa, og Koshu Kaido førte til Shimosuwa i nutidens Nagano-præfektur, som desuden var et stop på Nakasendo.
Dyredrevet vognkørsel var i en stor del af Edo-perioden forbudt, og mange rejste derfor til fods, hvilket betød, at folk tilbragte mange dage på Gokaido. Af den grund blev der på ruterne anlagt såkaldte stationer bestående af mindre gennemgangsbyer kendt som shukuba, hvor rejsende kunne gøre hvil og indtage mad på beværtninger for at gøre deres færd så behagelig som mulig. Men dette var dog også for at kontrollere folkevandringen, for i en shukuba kunne man også risikere at skulle registrere sig og blive visiteret, og derfor foregik der et tæt samarbejde med shogunatet, hvilket var grunden til, at en shukuba havde sit eget officielle hovedkontor, der eksempelvis modtog efterlysninger på personer, man skulle holde øje med, ligesom man kunne indberette folk.
En shukuba var et sted, hvor rejsende kunne mødes og udveksle historier og viden, hvorved de kunne blive gjort klogere på, hvad der skete rundt omkring i landet, og man kunne dermed også etablere nye bekendtskaber. Mens almindelige mennesker skulle betale for et ophold på vandrehjem kendt som hatago, hvor man enten fik et værelse eller en plads i en fælles sovesal, så kunne højststående personer og samuraier derimod overnatte gratis i bygninger kaldet honjin, der var indrettet som private boliger, så man derfor også kunne opholde sig i private rammer. Herudover fandtes der også butikker, hvor man kunne købe forskellige ting, og tehuse, hvor man kunne få noget at drikke eller spise, så en shukuba nærmest var en lille landsby bestående af erhverv. Anlæggelsen af shukuba førte derfor også til udviklingen af flere byer, som endnu eksisterer den dag i dag, og det samme gør nogle af de gader, der i sin tid udgjorde en shukuba.
Eftersom shukuba var tænkt som et stop på Gokaido, så blev denne opdelt med udgangspunkt i antallet af shukuba - eller stationer, som de også kaldes. Tokaido bestod af i alt 53 stationer og forbandt Edo med Kyoto langs kyststrækningen ud mod Stillehavet, men delte dog de sidste to stationer med Nakasendo, som derimod bestod af 69 stationer og forbandt Edo og Kyoto via en indlandsrute. Med en længde på 534 kilometer var dette den længste af de fem hovedveje, hvorimod Nikko Kaido var den korteste. 17 af de 21 stationer på denne blev nemlig delt med Oshu Kaido, der havde i alt 27 stationer og havde til formål at forbinde Edo med datidens Mutsu-provins, der var betegnelsen for de nordlige egne af Honshu. Koshu Kaido fungerede som nævnt som en slags smutvej til midt på Nakasendo og bestod af 44 stationer. Ruterne havde eksisteret, længe før de blev gjort til deciderede hovedveje, og de fungerede som udgangspunkt for de moderne vejnet og jernbaneforbindelser, der i dag forbinder de samme områder med hinanden.