In Tokyo Station, lockers and baggage rooms sit on more than one level and on both the Marunouchi and Yaesu sides, so the useful question is not whether the station has storage, because it does in several places, but which side and which level you want to be standing on before you start walking. The reliable way to get there is to find a concourse map panel or an information counter, read the coin locker or baggage room icon out of the map's legend, and anchor the location to an exit number instead of a shop name.

I know that sounds like a small thing until you are the person standing still in a moving crowd.
Picture the version of this I keep repeating. I come up the escalator off a platform with a 26-inch suitcase that has one sticky wheel. The concourse is bright and low-ceilinged. A bakery is pushing warm air across the walkway. The departure board above the gates clatters as it flips. Everyone around me is moving at the same steady speed, and every one of them knows where they are going. I am the only person not moving. That is the moment the station punishes, not the walking, the standing.
What I have learned is that Tokyo Station answers any question you ask it in the right form. The wrong form is "where are the lockers." The right form is "which exit am I nearest, and what is marked next to it."
Start at the map panel, not at the first locker bank you see
Every major station here posts concourse maps that carry several languages, and the ones at Tokyo Station are usually mounted on pillars or on the wall near the gates. They are drawn as a flattened diagram of the station, which is confusing for about ten seconds, and underneath that diagram is a legend.
The legend is the whole point. Coin lockers get a small square icon, sometimes with a key inside it, sometimes just a tiny box with a line under it. A baggage room, the staffed kind, gets a different mark, often a suitcase or a counter symbol, and the legend spells it out. I do not trust my memory of which icon is which from one year to the next, because the map is redrawn when the station renovates and the icon set shifts with it. I read the legend every time.
If the panel is crowded or I am too tired to parse it, I go to an information counter and ask a person. This is the part most visitors skip. Staff at the counter will take a pen and mark the nearest storage point on a paper map and hand it to me. That paper map is more useful than anything on my phone, because it is current and it is the same map the staff use.
Exit numbers outlive every shop name in the building
The single most useful habit I have built here is describing locations by exit, not by landmark. Shop names change. Pop-up counters rotate through the concourse on a seasonal schedule. "Next to the bakery" is a sentence with a shelf life. "Near the Yaesu Central Exit" is a sentence that survives a renovation.
Exit signs are not just for leaving. They are the station's own coordinate system, and the staff use it too. When I ask a question and the answer comes back as an exit name or number, I know it is a real answer and not a guess.
Why the corner by the restroom is usually the answer
Locker banks are not usually out in the main walkways. They are clustered in the corners, near restrooms, near ticket gates, and near exits. There is a practical reason for that. Commercial space in the middle of a concourse is too valuable and too busy to fill with metal boxes, and fire codes care about keeping the main flow of people clear. Restrooms already occupy the awkward plumbing corners, so the space around them is where the storage tends to go.
When I walk into an unfamiliar concourse, I do not scan the middle. I look at the edges, and specifically at the edges near a gate or a restroom door, because that is where I have found nearly every bank I have ever used.
Tokyo Station stores bags on more than one level
The mistake I made early on was treating Tokyo Station as one big room with one storage area. It is not. There are lockers near the Shinkansen gate area, there is storage in the Yaesu side concourse, and there are banks at other levels and on the Marunouchi side as well. The exact position of a given bank moves when the station is under construction, which is exactly why I read the map instead of trusting what I remember from a previous trip.
Practically, this changes how I plan. If I am arriving on the Shinkansen and continuing on a local line, I want storage inside that flow, not across the station. If I am meeting someone on the Yaesu side, I want the Yaesu side. Deciding the side first eliminates half the walking.
Staying inside the gates, and what leaving costs you
This is the part that saves real money. The paid area and the free concourse are different zones, and the connections are not the same on each side of the gates. If I have already passed through a ticket gate, walking back out and then back in is not free and not always simple. The ticket in my hand was validated for one entry, not for a day of wandering. With an IC card I get tapped out and charged, then charged again to come back in. With a paper ticket I end up at the gate window explaining myself.
So the order of operations matters. If I am coming from outside the station and I need to store a bag, I store it before I pass through a gate. If I am already inside and in transit, I use the storage that is inside, even if a bigger bank exists outside. Twenty minutes of extra walking to save a five-minute difference in locker size is a bad trade.
The baggage room is a counter, not a locker
A locker is a box you feed and walk away from. A baggage room is a staffed counter where a person takes your bag and gives you a receipt, and it handles the things that do not fit in a box at all, which for me has meant a stroller, a golf bag, and a suitcase that was too tall for the largest locker row.
It is a different transaction with different tradeoffs. It has staffed operating hours, so it can be closed when my train is not, and those hours are not something I would trust from a blog written two years ago. The counter may also have quantity limits during busy travel periods. I treat the baggage room as the answer for oversized items and for the days around major holidays, and I confirm the current hours on the day, in person or at an information counter. It is also the thing I check first if the locker bank I found is full, because it is the fallback that does not require me to leave the station.
Shinjuku needs a different first move
Shinjuku is the station where the exit count defeats people. There are so many exits, and the gates are spread across a footprint that barely feels like one building, that hunting for a locker after you are already inside is the wrong order.
My first move at Shinjuku is to identify the storage zone before I go near the gate area. I find the map, I find the icon, and I note which exit it belongs to. Then I decide whether my train leaves from a gate near that zone or from a completely different part of the station. If those two things do not line up, I store the bag on the side I am leaving from, even if the other side looks better on the map. The scale of the place means that fixing a wrong decision costs more than it does anywhere else in the city.
How to describe a storage spot to someone else
When I split up from the people I am traveling with, I do not say "I put the bags in a locker." I give them a line with five parts, in this order:
- The station name
- The side, such as Marunouchi or Yaesu
- The level, or the name of the concourse
- The nearest exit name or number
- The landmark the bank sits against, usually a restroom or a gate
Something like "Tokyo Station, Yaesu side, ground level, near the Yaesu Central Exit, in the corner by the restrooms." That sentence works over a phone with bad reception, and it works for a stranger at an information counter.
When the bank you found is full
I am not going to tell you which bank has space on the day you arrive, because nobody knows that and anyone who claims to is guessing. Lockers at the biggest stations fill, especially in the morning and especially during travel season. That is the honest limitation of this whole system.
What I do when a bank is full is run the options in a fixed order instead of panicking. I check whether there is another bank on the same side, since maps often show more than one. I check the staffed counter. I look at the level below or above, because the bank by the Shinkansen gates and the bank in the underground concourse do not fill at the same rate. And if all of that fails, I stop treating the station as the only place to put a bag and look at my hotel or a locker one stop away. The point is to have the order decided before I need it.
What I check before I walk away
Two things, every time.
First, how the locker wants to be paid. Some take coins, some take an IC tap, and the panel on the door tells me which. I do not want to learn that at the moment I am trying to catch a train.
Second, I take two photos with my phone. One of the locker number and the bank itself, one of the exit sign closest to it, taken from the direction I will be coming back. The concourse looks completely different from the opposite direction. The photo of the exit sign is the thing that gets me back to my bag, and the photo of the locker number is the thing that gets me the right door when there are forty identical doors in a row.
That is the whole skill. Not knowing where the lockers are, but knowing how to ask the station, in the station's own language of icons and exit numbers, and then writing the answer down before you move.