Veganism does not have a large awareness in Japan today and most health-focused restaurants are closer to pescatarian, pesco-vegan, or macrobiotic than true vegan. Katsuobushi, a dried, smoked, and fermented fish, is used to make a soup stock called "dashi" which can and will be hidden in almost everything.
Eating plant-based in Japan is incredibly easy. Eating vegan is incredibly hard. You are going to make mistakes, it's not the end of the world, learn from them and try to do better next time.
In the 9th century, the Japanese Emperor Saga, under the influence of Buddhism, made a decree prohibiting meat consumption (excluding fish and birds). This remained the dietary habit of Japanese until the introduction of European dietary customs in the 19th century. However, seafood, and especially a dried and fermented form of Tuna known as katsuobushi (or sometimes "bonito"), has always been consumed to some extent and the Emperor's edicts either never reached or were not followed in all areas. For some communities, "fish" included whale meat and in mountainous areas game and wild boar would be included.
From the 12th century onward Zen Buddhism de-emphasized the importance of vegetarianism, although as most people in Japan were peasants their diet remained virtually vegan.
In the 20th century The United States of America took charge of rebuilding Japan after WWII, sending food aid to combat hunger and childhood malnutrition, and introducing a generation of Japanese to mass consumption of animal products. Like the school lunch program stateside, food aid to Japan was a dumping ground for agricultural surpluses: powdered milk, government cheese, processed meats.
Buddhist temple food is called "shojin ryori" and can be either vegetarian or vegan. It is an exquisite and ceremonial cooking still served traditionally at temple inns such as those in Mount Koya, Wakayama.
Notable too is Daitokuji Ikkyu  at the Daitokuji Temple in Kyoto, a restaurant has been preparing vegetarian shojin-ryori since the mid-1400s surely making it the old veggie restaurant in the world. It serves dinner as well as lunch from Y4000 to Y8000.
Shojin ryori is not a Japanese synonym for "vegan". Describing yourself as shojin ryori or asking for shojin ryori cuisine to be served to you outside of a Buddhist temple or restaurant specializing it will just garner you confused, "stupid foreigner" stares. You are not a monk and their restaurant is not a temple.
Influence of the WestEdit
Under the influence of Western traders Japan was introduced to the idea of a meat-centric diet starting in the 19th century, and then under the American effort to rebuild Japan after WWII large amounts of low-grade dairy was sent to Japan as food aid. In Gyokusen-ji (3 hours South-West of Tokyo) there is a memorial statue to the first cow slaughtered for its meat, dated to the late 19th century and attributed to the influence of the first American Consul General, Townsend Harris (1804-1878).
More and more Japanese are relying on meats, dairy and junk food for their calories. "Super-sized" hasn't taken off in Japan yet, but there are McDonalds and local MOS(Mountain, Ocean, Sun) Burger chains across the country. As Japan's wealth increase in the boom periods, so did its diet become far richer in animal products and imported food stuff. Japan is an important market for American and Australia beef industries.
Alternatively, more recent Westerners, and Japanese travelers to the West, have introduced typical wholefood shops and distributors such as Waraba Mura and Alishan. Both are now run by Japanese.
The Japanese diet includes numerous specialist foods that are very healthy and interesting contribution to a vegan diet and which have influenced it through the spread of the pro- but not exclusively macriobiotics. For example; miso, natto, many varieties of tofu, yuba, amazake, goma-tofu (sesame tofu), a wide variety of grains, and gluten products such as fu, pickles, seaweeds, noodles, beans unusual vegetable are widespread. Dried fruit and nuts are not and are very expensive but high quality. Fruit and vegetables in general are also very expensive and tend to come "gift wrapped'. The $200 melon is not a myth! Care needs to be taken not to buy foods that look innocent but include bonito. Home cooking benefits hugely.
Numerous regular food scares happen relating to lower quality Chinese foods relating to the over use of pesticides and illegal additives.
Wholefood shops Edit
There is a chain of healthy food shops in many large cities called Natural House, and another more macrobiotic (selling organic animal produce) called Anew where most staples can be bought.
Almost all miso soup contains bonito or other animal products, even in some vegetarian cafes. You might have better luck in the mountainous regions where shiitake mushroom stock is used instead. Bonito imparts a smoky, umami taste. If you're not sure if you're consuming something made with bonito, look for a smoky taste, as the umami taste can be (although rarely is) substituted from other things (seaweed, mushrooms, tomato, straight up MSG).
Udon (wheat noodle) and Soba (buckwheat) bars are ubiquitous and appear hopeful but they are either served in a dashi (fish broth) soup, or with a tsuyu (sweet and salty) dipping sauce that is also made with dashi. It is possible to request just plain noodes and add your own ginger, shoyu (soya sauce) etc.
You can order your soba or udon "oroshi-shoyu" style which is cold noodles with grated daikon, green onion, a slice of citrus, and then soysauce poured over. However some places will dilute their "special soysauce" with dashi.
The batter is often made with eggs, and if you don't speak Japanese or see them make it just assume it does. However, egg-free tempura is by no means rare.
The dipping sauce for tempura is not vegan as it contains dashi. The sauce poured over a "tendon" (don is a rice bowl, so tendon = tempura rice bowl) is just a thicker version of the dipping sauce and is also non-vegan.
Almost all tempura is fried in the same oil as animal products.
Traditional Japanese sweets are largely vegan, especially those made with mochi (sticky) rice and azuki bean paste. Also included are warabi mochi, made from a fern root, kanten (a jelly made from seaweed gelatin). Dango (mochi that is shaped as a ball) is also vegan.
All bread in Japan can be assumed to contain dairy. Most breads are either soft, spongy, and cakey like wonderbread, or sweet and eggy like brioche. High gluten, hard, winter wheat does not grow in Japan, so European style (ie. crusty, chewy) bread is rare, although French-style bakers and the odd wholegrain natural rise breads can occasionally be found in big cities.
Apart from the ubiquitous and many varieties of tofu that are available locally and freshly made, there are many other soya products from edamame (green soya beans often served with beer), yubu (the skin taken off cooking soya milk), fresh soya milk, natto (fermented soya beans eaten generally at breakfast), gomatofu (tofu with sesame seeds, some icecreams and tempeh etc.
Be wary as soy-based foods are not guaranteed to be vegan by default, and they are not marketed as alternatives for people who do not eat dairy, but rather just as soy because people in Japan like soy. Some soy milks are actually mixed with dairy, and tofu hiyayakko (cold tofu) and agedashi (fried tofu) are often garnished with bonito. Tofu ice cream exists, but it's dairy based and just flavored like tofu. Kitsune Udon (noodle soup topped with fried tofu), will be served with a fish-based broth.
Sushi trains are a good option because you can see what you're getting. Most also have menus you can choose from. Cucumber, dried gourd, pickled daikon, pickled or fried eggplant, natto, and inari are common on most menus, however the full compliment of veggie options might not be making the rounds on the conveyor belt and you'll likely need to order a la carte. Be wary of corn, as it's likely smothered in mayo.
Japanese curry sauce, even if it does not contain obtusely contain meat, can be assumed to contain meat, animal fat, and dairy derivatives. However, CoCo Ichibanya Curry House has a "low allergen" curry which is guaranteed to be vegan. They serve you a packet which you have to open yourself (to avoid contamination), but you can choose vegetable add-ons from the normal menu. The low allergen curry is listed on the menu but not the ordering cards, you have to ask about it separately.
While many people visit Japan and come back raving about the ramen, there is literally nothing in a typical ramen restaurant that a vegan can eat. The soup is meat based. The gyoza are meat based. There are no salads or side dishes to jury-rig a meal from. As a vegan there is no reason to even go into a ramen restaurant, however if you're traveling with mixed company and they want to go into a ramen restaurant, at least get a beer (or soft drink). It's rude to take up a seat in a restaurant when you didn't order anything.
Vegan-friendly shops, restaurants and cafes Edit
- Crayon House - Omotesando - Famous bookstore, organic store and cafe/restaurant. A small world/community. Broad selection of organic food and a nice lunch buffet.
- Pure Cafe - A small and rather fashionable cafe attached to a natural cosmetics store. Small but nice menu. Portions are slightly small so maybe order extra side dishes. Cafe does not take reservations.
- Brown Rice Cafe Omotesando - Right across the street from Crayon House. Smaller, newer and fancier than Crayon House specializing in a broad range of drinks and teams as well as brown rice. Interesting menu featuring a veggie burger and curry rice.
- Yasai-ya Mei - Omotesando - Located in Omotesando Hills. Japanese style dishes with organic vegetables.
- Mominoki House - Sendagaya, Harajuku - This old estabilished organic restaurnat, which been in business since 1976, has a variety in vegan dishes. It opens for lunch and dinner.
- Gaya - Yoyogiuehara - "Izakaya"style restaurant. Organic vegetables. There are also branches in Aoyama, Tachikawa and in California, US.
- Vegan Healing Café Shibuya café review. Haven't tried it yet, but it looks promising.
- Cafe Eight - Aobadai, Meguro - Run by the same company as Pure Cafe. Catering and online shopping available. http://www.cafe8.jp/
- AEN - Jiyugaoka - Organic restaurant. There's a branch in Shinjuku Isetan Departmentstore.
- Fangsong café Akasaka - Small, organic/vegetarian café on a back street in Akasaka. Very good and fairly cheap. Web page in Japanese, map: 
- Daigo - Toranomon - Located in Atago Hills. This high-class Japanese style restaurant serves "shojin ryori" courses (starting with 10, 000 JPY) in private rooms.
- Inakaya - Roppongi - "Robatayaki" grill restaurant. Not a vegan place but various kinds of grilled fresh vegetables available. They perform a "mochitsuki" rice cake pounding show two times a day. Popular for Hollywood stars.
- Shizenshiki Shokudo KeKe - Ginza - Across the streeet from Plantan Ginza - Buffet-style restaurant of organic vegetables, chemical seasoning and preservatives-free dishes. There are also branches in Haneda Airport, Setagaya, Yokohama and Saitama.
- Chaya Macrobi Cafe&Deli - Hibiya - Macrobiotics delicatessen and cafe.
- Govinda's Nakano. "Pure vegetarian restaurant non violence food—Our dishes doesn't any meat, fish, onion, garlic, alcohol and caffein."(sic)
- Monk's Foods in KichiJoji - This is not a vegetarian or vegan restaurant per se, but it's organic and macrobiotic and he only serves 3 options a day, one of which can be prepared vegan on request.
- der Akkord - A small but famous bakery for vegans, serving variety of breads, cakes and pies. Online-order available.
- hifumi organic cafe and foods - Chiba-shi - organic cafe/restaurant and shop serving vegan and macrobiotic foods. Every Thursday there is an organic food market outside of the cafe/shop with fresh, organic produce from local farmers