If you don't mind seeing all the dead fish, sushi can sometimes actually be a possible option for vegans and vegetarians. The fishless options are the cheapest but sweetest. Order Kappa-maki (cucumber roll), O-shinko-maki (pickled vegetables, usually yellow Japanese radish), Natto-maki (fermented soybeans roll), Kanpiyo-maki (pickled gourd roll) and some places also have Inari (sweet rice wrapped in thin deep-fried tofu), Ume-maki (sour pickled plum, sometimes with cucumber), Horenso-maki (spinach roll), and other sushi made with different kinds of seaweed on rice. Some of these come with fish flakes sprinkled on top, so ask for 'katsuo-bushi nashi' to hold the fish flakes. Tamago (sweet egg on rice) usually contains fish stock. Some sushi restaurants also serve konyakku sashimi (thin slices of gelatinous yam paste), salads and seaweed soup which might also be ok. Sushi restaurants often have pictures on the menu. You'll find more veg options at a large sushi restaurant of course. Even at kaiten-zushi (conveyer belt sushi) restaurants, you can order things made fresh if nothing veg comes past.

Take a look at some recommended Japanese restaurants in Tokyo. 

Tempura is deep-fried battered seafood and vegetables. Most tempura places will have yasai tempura (vegetables only) on the menu. Eggs are used in the batter so it's not an option for vegans. The vegetables are also of course fried in the same oil as seafood. Skip the miso soup as it probably contains fish stock. The tempura sauce might too, so ask for it "shio de" (with salt) and use salt or soy sauce instead. Don't put the sauce or salt on the tempura, but dip the tempura in it. Common vegetables in tempura are nasu (eggplant/aubergine), Shiitake or other mushrooms, imo (sweet potato), kabotcha (pumpkin), renkon (lotus root), and onion. You'd be better to order a la carte because the sets usually contain miso soup and a kind of egg pudding made with fish stock. Tenya is a cheap fast-food-style tempura chain easily recognised by its blue and yellow signs.

Take a look at some recommended tempura restaurants in Tokyo.

Okonomiyaki is like a big fat pancake with cabbage and seafood or meat. Most places should be able to make it sans meat and seafood. Egg is used in the batter so it's not suitable for vegans. Usually, you cook it yourself on a hot-plate or it is cooked in front of you. For vegetarians, it's basically just cabbage and batter, but depending on the style of the restaurant, you can ask for other ingredients like soba noodles, kimchee, mushrooms, etc. One problem is that apparently some okonomiyaki restaurants use lard on the hotplate so try to find one which doesn't or be so bold as to ask them to use vegetable oil instead. Another problem is that okonomiyaki sauce sometimes contains fish, so you could ask for it without sauce. Also, they sprinkle fish flakes on it, so remember the magic phrase, 'katsuo-bushi nashi!' ("without fish flakes") Okonomiyaki restaurants also have other side dishes like enoki mushrooms cooked in butter. Monja, the Tokyo equivalent of okonomiyaki is similar, but sticky and runny.

Take a look at some recommended Japanese restaurants in Tokyo.

Ramen, a Japanese version of Chinese noodles in soup, has recently become extremely popular in Japan. Unfortunately, ramen shops are never a possibility for vegetarians though because chicken/bones/meat/fish are always used to make the soup. Similarly, all Japanese instant ramen available in supermarkets contains animal products. However, you can buy fresh ramen noodles and make your own soup, and health food shops and international grocery stores often stock veg-friendly instant ramen. The other two kinds of noodle shops you'll see everywhere are udon (thick flat noodles) and soba (buckwheat noodles), but when served hot, the soup always contains fish or meat. Cold soba could be a possibility if you skipped the soba dipping sauce and used soy sauce instead. Of course, like ramen, you can easily make it yourself.

Take a look at some recommended Japanese restaurants in Tokyo.

Izakayas are Japanese-style sit-down bars which serve various kinds of Japanese and Japanized food to share while drinking. If you look around, you should be able to find one which has a few veg options. You might be pushing it to have a complete meal though. Some izakaya standard dishes which might be ok for vegetarians include edamame (boiled young soybeans in the pod), yakko (cold tofu - ask for it without fish flakes), tsukemono (pickled vegetables), onigiri (rice balls - ask for ones with umeboshi (sour plum) or konbu (seaweed) inside) or yaki-onigiri (grilled rice balls), salads, and fried potatoes. Because izakayas serve such varied food, you might be lucky to find pizza, pasta, tofu dishes, okonomiyaki, grilled vegetables, rice and noodle dishes, and other things on the menu which may be edible. Other bars serve a similar range of snacks and small dishes. These are the best places to try sake or sho-chu. The small izakayas are the best for authenticity and atmosphere, and the staff will be more willing to try to cater for you. However, the big chains like Shirokiya, Watami, Wara-Wara, Doma Doma etc have picture menus.

Take a look at some recommended Japanese restaurants in Tokyo.

Yakiniku is a cuisine that came from Korea. Although these are restaurants specialising in grilled meat, you can sometimes find ones with a surprising range of veg-friendly choices. You'll have to put up with the smell of burning flesh, and insist on a seperate grill than your meat-eating friends, as in these places you cook the food yourself. Check out the menus and sometimes you'll find vegetables to grill (usually mushrooms, capsicum/green pepper, onions and eggplant), plus side dishes like salads, kimchee, etc.

Take a look at some recommended Japanese restaurants in Tokyo.

Although they sound promising, tofu restaurants mostly serve tofu dishes containing fish or meat! Most of them usually have a couple of items which are ok though, but tend to be expensive.

Search this site for recommended veg-friendly tofu restaurants in Tokyo.

Shojin-Ryori is Buddhist vegetarian cuisine served at temples and special restaurants mainly in the Kyoto area. It's a very zen experience with beautifully presented and subtly-flavoured set meals. However, it's usually extremely expensive so not the kind of food you could eat regularly! There are only a couple of these restaurants in Tokyo.

See the Japanese restaurant listings for some shojin-ryori restaurants.

SHABU-SHABU, SUKIYAKI, YAKITORI, TONKATSU, TEPPANYAKI, JAPANESE CURRY, GYUDON, ODEN, etc
It's almost impossible to find suitable food at these kinds of restaurants.

 Take a look at some recommended Japanese restaurants in Tokyo.

Indian restaurants are a Tokyo vegetarian's best friend. Luckily, there are many Indian (and some Bangladeshi, Pakistani, Nepalese, Tibetan, Sri Lankan) restaurants around Tokyo. These places always have vegetarian and sometimes vegan options, and the staff usually speak a bit of English. They can be a bit pricey though, so it's best to go at lunch time when most have lunch buffets or sets for around 1000yen. Whatever you do, don't confuse a Japanese curry restaurant for an Indian one. Japanese curry is not suitable for vegetarians! See the Indian Restaurants list in the Restaurants section for some recommendations.

See the Indian Restaurant listings for some recommended Indian and South Asian restaurants. 

You won't have trouble finding Italian restaurants in Japan. If you can eat cheese, pizza is a good option as most places have a few meatless pizzas, or others that you can ask for without meat. There are usually meatless pasta dishes like tomato, arrabiata, pepperoncino etc. But sometimes they contain bacon for some reason, so ask for 'be-kon nashi.' A problem with pasta is that sometimes chicken or beef stock is used in the sauce, so it's good to ask, and avoid the soupy pasta dishes. Try to find the more authentic Italian restaurants for more vegetarian choices. Sometimes Japanese-style spaghetti (made with soy sauce, nori, shiso/mushrooms/spinach/kimchi/natto/etc) suitable for vegetarians can be found, but again check if they use fish or animal stock. Unless you can communicate well with the chef, vegan options can be limited in Italian restaurants.

Search this site for recommended Italian restaurants in Tokyo.  

If you're lucky, you might come across a Israeli, Turkish, Lebanese or other Middle-Eastern restaurant which has some vegetarian-friendly food. Unfortunately, most kebab vans you see around don't sell felafel!

Search this site for recommended Middle Eastern restaurants in Tokyo.

There aren't that many Mexican restaurants in Japan, especially not authentic ones. Most of them have a few things suitable for vegetarians though, such as bean burritos or vegetable fajitas. There are some Tex-Mex, American, and Fusion restaurants around which serve Mexican food.

Search this site for Recommended Mexican restaurants in Tokyo. 

Chinese restaurants might seem ok, but most have been Japanized and unless you find an authentic place where you can communicate well with the chef, they are best avoided. Generally all dishes contain seafood or meat, or at the very least, chicken stock.

There are some good vegetarian Chinese and Taiwanese restaurants in Tokyo, so search this site for recommended Chinese and Taiwanese restaurants in Tokyo.

There are a few Thai, Vietnamese, Indonesian, or other South-East Asian restaurants around but it can be a bit difficult to find veg food. Shrimp paste or fish sauce are often used. Korean might be an option if you could ask for bibimba without meat, grilled vegetables, or side dishes like kimchee. American restaurants and big chains like TGI Fridays sometimes have vegetarian options. British Pubs sometimes have vegetarian meals and pub snacks. African, South American, European and almost any kind of restaurant can be found in Tokyo, but vegetarian options are limited.

Search this site for recommended South-East Asian and Korean restaurants . 

You won't find any vegetarian food in any of the US or Japanese hamburger chains except maybe fries (remember, McDonalds uses beef extract in their fries). One exception is Mosbuger. Although their menu changes, there is usually at least one vegetarian-friendly burger on Mosburger's menu. Last time I went, they had a kinpira-rice burger and a konyakku burger. They also cook their fries and onion rings in clean vegetable oil. Subway is also a good option as you can choose what they put in your sandwich.

If you can eat cheese, there are some pizza restaurants around which have some meatless pizzas. And there are lots of pizza delivery companies like Pizza Hut, Dominoes, Pizza-La etc. Pizza delivery is expensive in Japan though. Try to find smaller local pizza shops as they are cheaper and nicer. There should be a couple of meatless pizzas on the menu, or other pizzas that you can ask for without meat. You'll also find some strange but surprisingly nice items on pizzas, like corn, eggplant, potato, and fruit.

Search this site for recommended pizza restaurants. 

There are heaps of little cafes around as well as the omnipresent Starbucks, Doutour, Tully's, Excelsior, Veloce etc. They sometimes have sandwiches, muffins etc which are ok. Look for the more bohemian cafes or cafe/bars because they are more likely to have vegetarian options. A lot of Japanese cafes often serve light meals like spaghetti which are sometimes ok.

There are lots of great vegan, vegetarian and veg-friendly cafes in Tokyo so have a look at the recommended cafes listed on this site.

You'll find Johnathon's, Denny's, Royal Host, Skylark, Gusto, BLDY, various other chains and small Western-style cafe-restaurants everywhere. These are places to go for drinks and desserts mainly because food for vegetarians is fairly limited. Chips, salad, and pasta can usually be found. Saizeriya is an Italian-style family restaurant which offers a few more veg options than the others.