At the moment I’m sitting in a cottage in France (recovering from a cold, but that’s another story), a land notorious for not being so vegan friendly except in the larger cities. The native cuisine is generally not vegan - even vegetable dishes often use things like dairy products or animal fats or stock in the cooking process, which can make things difficult. But if you are a vegan you probably know about this, and come prepared accordingly. (I think it’s a lot easier for lacto-ovo vegetarians in France; you could live on the delicious bread and cheese.)
If you are going to Japan, you might think that being vegan would be a lot easier. Japanese cuisine has a reputation for using lots of vegetables, seaweed and other vegan-friendly products. There is even a particular kind of cuisine in Japan called sho-jin ryouri (精進料理）, a mostly vegan temple cuisine, with a long and highly regarded tradition.
But as a reader who emailed me recently found out, being vegan in Japan is just as hard as it is in Europe.
I don’t have any numbers in front of me, but I am guessing that there are far more vegans or vegetarians in North America and the UK than there are in Japan as a percentage of the general population. According to this article in the Japan Times , most Japanese people, even those that frequent vegan/vegetarian restaurants, do so for health reasons rather than ethical or religious reasons (and most aren’t veggie 100% of the time). Generally speaking, the Japanese diet is based on fish, sometimes poultry and eggs, rice, legumes (pulses, beans) and vegetables, with meat and dairy being a later addition.
Traditional Japanese cuisine, or washoku, is very healthy (the only thing you should watch out for really is the high salt content in some dishes). It uses lots of vegetables, seaweed, legumes and so on, with a relatively small amount of protein from fish or meat. However, one thing that makes it almost impossible to be a vegan in a traditional Japanese restaurant is the fact that dashi is used in practically everything. Here is my recipe for basic dashi ; as you can see, it contains dried bonito (fish) flakes, or katsuobushi. All regular dashi recipes specify the use of katsuobushi or niboshi (dried fish). Even dashi granules, unless specified otherwise, contain bonito extract. There are dashi granules made from seaweed sources only, but these are not usually used in restaurants.
Dashi is not only used in the obvious places like soups and stews. It’s used in just about every savory dish. It’s used in dressings and sauces for vegetable dishes, as a cooking liquid for sushi rice, in dipping sauces, as a ‘hidden flavor’ (kakushi aji 隠し味) and so on. Just about the only things that are fairly sure to be dashi-free are plain rice and homemade pickles. Even things like umeboshi (pickled plums) often have some dashi added to them.
Ironically the only vegan umami flavor additive is probably pure MSG (the most common Japanese product name is Ajinomoto), which is made from soy beans. But the better a restaurant is, the less likely they are to be using straight MSG in their cooking. A better establishment would make their own dashi, and a cheaper one would most likely use dashi granules.
The use of dashi takes nothing away from the fact that traditional washoku is very healthy. For omnivores, I can’t think of many other cuisines that are better for you. But of course if you can’t eat fish in any form for whatever reason, the omnipresence of dashi can pose a problem.
Some regional cuisines like Okinawan cuisine use a dashi made of fish and pork or chicken. (Okinawan cuisine relies a lot on pork.)
Sure, you could. You would need a very generous budget though. Sho-jin ryouri is Japanese haute cuisine, and a typical meal at a sho-jin ryouri restaurant can set you back 10,000-20,000 yen per person or more. (You might have luck finding less expensive places in the Kyoto/Nara area or from some temples open to the public.)
So what if you were to avoid washoku altogether in Japan, and stick to ‘western’ style food? That can be a problem too. The reader who sent in the question was having a very hard time finding any vegan bread. In Japan, mainstream bread usually uses white flour, butter, and/or eggs. You can find things like baguettes and hard rolls that are probably butter-free, but you would have to ask. Whole grain breads are slowly gaining in popularity, but usually a ‘whole wheat’ bread in Japan means something with 10% or so of whole wheat flour, with the rest being white flour.
Japanese-style western cuisine or yohshoku  is largely based on traditional French cooking techniques. So, the better yohshoku restaurants rely heavily on the use of properly made beef stock and demi-glace. (A pot of carefully prepared demi-glace is a badge of honor for a good yohshoku restaurant or cafe.) Besides the fact that most yohshoku dishes are meat or egg based anyway (beef stews, curries, omurice , etc.) this is not a good choice for a vegan or even a vegetarian.
For eating out, there is the Japan Vegan Restaurant Pocketguide  in English - they say the new issue is due out in March. You can also try looking for macrobiotic restaurants (マクロビ or マクロビオティック). The aforementioned page on The Japan Times site  also has a small list (though it’s from 2007, so check before you go.) And treat yourself to an authentic sho-jin ryouri restaurant at least once!
But if your stay in Japan is more long term, as in many countries your best bet is to cook for yourself. You can even cook washoku for yourself, using vegan dashi. Use my vegan dashi recipe , or find konbu seaweed based dashi granules. There are all kinds of interesting vegetables in Japan for you to try, as well as different kinds of beans an legumes (dry or canned). And of course, there are the many varieties of tofu. If you can, get tofu from a tofu-ya (tofu store) that makes their own. Freshly made tofu is just amazing.
Try to eat brown rice instead of white rice. You can find all kinds of brown rice in Japan, some of which can be cooked exactly like white rice with no extra soaking time and so on. In fact, as a vegan in Japan you’ll want to base your diet around brown rice and zakkokumai  rather than whole grain baked products, if only for the fact that rice is much easier to find. You can even buy things like microwaveable brown rice or brown rice porridge; even a tourist can take advantage of these handy products.
If you can’t find things like whole wheat bread at your local supermarket or konbini (convenience store), try the food halls of department stores, or look for natural food stores.
Lawson, the konbini chain, has a new ‘concept’ store chain called Natural Lawson. While they are not necessarily vegan or vegetarian, they purport to carry things like organic, low calorie and ‘natural’ products. List of stores (in Japanese) ; so far only in the Tokyo/Kanto area.
If you are in Japan long term, investigate joining a farming coop (農協）in your area, or just signing up for a national one that ships their products. Ask your neighbors, or look in magazines like Kurowassan (クロワッサン (Croissant)) which often has special issues on macrobiotic or vegetarian/vegan cooking, natural healing and such. There’s also a quarterly magazine called Veggy STEADY GO! that you can look for.
Incidentally, you can rest assured that any Japanese or not-Japanese recipe categorized as vegan on Just Hungry  or Just Bento  will really be vegan! For Japanese recipes, I always make sure to use vegan dashi .