Fish recipes – 9 favorites from our travels and our kitchen

Writer: Helena Bergström

Updated: October 2026 | We love to eat fish, both at home and when we travel. And just like with so many other foods, a particular fish dish can become strongly associated with a place or a trip. A simple tuna sandwich can take us back to Malta, haddock to Iceland and a fish sandwich to northern Germany.

Here we have collected nine of our favorites. Some we have discovered on our travels and then brought home with us, while others are old favorites that make us think of a special place or time in our lives. The recipes are not particularly advanced – after all, we are a travel site and not a food blog – but they are dishes we enjoy and are happy to return to.

Fish dishes that evoke travel memories

Food is an important part of traveling for us. We like to try local specialties and order something we haven't had before. But it doesn't have to be the most elaborate meal at the finest restaurant that sticks in the memory.

Sometimes it's a simple sandwich, a whole fish on the grill, or something you buy at a market and cook in your camper. Then you get home, try to recreate the taste – and suddenly the dish has become a part of your own kitchen. Here are nine such fish favorites for us!

1. Malta sandwich with tuna, capers and onion

We discovered this sandwich in Sliema in Malta and we liked it so much that we ate it several times during the trip. It was nothing special at all: bread with tuna, chopped onion, capers, sliced olives and olive oil. But oh so good!

When we got home we tried to recreate the sandwich and it has stuck with us ever since. The flavors still make us think of Malta.

In Malta there is a tradition of bread that is flavored with olive oil and various Mediterranean ingredients, but we do not claim that our sandwich is an exact Maltese classic. This is simply our version of the sandwiches we ate in Sliema.

You will need

• a good bread
• canned tuna
• yellow or red onion
• caper
• green olives
• good olive oil
• salt and pepper

Do the following

Chop the onion and olives and mix with the tuna and capers. Place the mixture on the bread and drizzle generously with olive oil. Season with salt and pepper to taste. It couldn't be simpler than that – and yet this is one of the fish dishes that brings back the most vivid travel memories for us.

2. Grilled seabream – Southern Europe on a plate

Grilled whole seabream is one of our absolute favorite fish dishes. It is a dish that for us is strongly associated with southern Europe, sun, sea and vacation. The fish can appear under different names on menus. In English it is often called sea bream and in Spain you may come across the name golden and in Sweden it can also be called gold sparrow. Regardless of the name, it is fantastic to put whole on the grill.

You will need

• 1 whole seabream per person, cleaned
• olive oil
• lemon
• salt and pepper
• possibly saffron
• optionally fresh herbs

Do the following

Rinse and dry the fish and make a few cuts in the skin. Rub it with olive oil, salt and pepper, and possibly saffron. Feel free to stuff a few lemon slices and fresh herbs into the belly. Grill the fish on both sides, on a grill or on the grill rack in the oven, until the meat is done and easily comes off the bones. Serve with lemon and simple side dishes.

Our favorite sauce: Mix crème fraiche with thyme, grated lemon zest, lemon juice, a little honey and possibly a drizzle of olive oil. The sauce also goes well with other fish such as salmon, rainbow trout, redfish or cod.

3. Boquerones two ways – a taste of Spain

Boquerones are small anchovies that are common in Spain, and we have learned to appreciate them in several different ways. During our long motorhome trip in southern Europe, we bought small boquerones and cooked them ourselves. It turned out to be a very simple dish where the small fish were fried and eaten with lemon. We like that kind of thing – local food that can be bought and cooked even in a small motorhome kitchen.

Fried boquerones

All you really need are small, cleaned boquerones, a little flour if you want them crispier, oil, salt and lemon. Lightly coat the fish in flour and fry or deep fry until nicely browned. Season with salt and serve with lemon.

But we also have a completely different boquerones story. Our friends Lennart and Beata once ordered in anchovies in vinegar ate at a Spanish restaurant in Sundbyberg. They were thin, almost white fish fillets that were served cold as a starter, with lemon, among other things. We were delighted and later made the same type of dish together at their home. Lennart and Beata now also live in Spain!

Boquerones en vinagre are anchovies marinated in vinegar and often served with olive oil, garlic and parsley. If you want to make it really easy, you can buy pre-marinated boquerones and serve them as tapas with lemon and other tasty accompaniments.

4. Grilled tuna – preferably red in the middle

We have eaten tuna at many restaurants during our travels, and Peter has a very definite opinion about how it should be served: red in the middle! Fresh tuna is something completely different from the canned tuna we used for the Malta sandwich. A nice piece of tuna doesn't really need much cooking or fuss.

You will need

• fresh tuna in thick pieces
• olive oil
• salt and pepper
• lemon or lime

Do the following

Dry the tuna and season with salt and pepper. Heat a frying pan or grill well and fry the fish quickly on both sides. We want a good sear on the outside but still plenty of red in the middle. Cut into slices and serve immediately, preferably with lemon or lime and a salad.

5. Homemade sushi – the restaurant favorite we took home

Sushi is a dish that we like to eat out at restaurants. But we have also made sushi ourselves at home – a fun little food project when you have the time and inclination. We do not claim to be sushi masters. You can delve as much as you want into rice, ingredients, knife techniques and different types of sushi. Our version is much simpler.

You will need

• sushi rice
• rice vinegar
• nori sheet
• salmon or other fish intended to be eaten raw
• cucumber
• avocado
• soya
• wasabi and pickled ginger if you like it

Do the following

Cook the sushi rice according to the instructions on the package and season with rice vinegar. Let cool.

Place rice and optional filling on nori sheets and roll up using a bamboo mat. Cut the rolls into pieces with a sharp knife. Or make it even easier and form small rice pillows and top with fish. It may not always look as pretty as in a restaurant – but it's fun to do!

6. Fischbrötchen – fish sandwiches from northern Germany

We have come across Fischbrötchen time and again when we have travelled in northern Germany. We have eaten fish sandwiches in, among other places, Hamburg, Wismar and on the island of Usedom, but also in Waren on the Müritz.

This is truly a food that goes with traveling for us. A Fischbrötchen is a simple fast food that is perfect for strolling around a harbor or along the water. The German fish sandwiches come in many varieties and can be filled with, for example, herring, matjessir, shrimp, smoked fish or salmon. Our own simple version is welcome to contain salmon.

You will need

• small rolls
• smoked or pickled salmon
• salad
• red onion
• cucumber
• remoulade sauce or other cold sauce

Do the following

Split the bread and fill with salmon, lettuce, thinly sliced onion and cucumber. Top with a little sauce. This is not intended as a recipe for the only ”proper” German Fischbrötchen – but as a simple fish sandwich inspired by all the ones we ate during our travels in Germany.

7. Haddock – a food memory from Iceland

Haddock is special to me (Helena) because the fish makes me think of Iceland. I lived on Hemön for a year., Heimaey, in the Västmanna Islands and there I ate a lot of haddock.

Haddock is somewhat similar to cod, but in Iceland I really learned to appreciate haddock. When I moved back to Sweden, I continued to buy this fish whenever I found it. It doesn't take much to make haddock delicious.

You will need

• haddock fillet
• butter
• lemon
• salt and pepper
• preferably boiled potatoes and vegetables for serving

Do the following

Salt and pepper the fish and fry it gently in butter until it is just cooked through and falls apart easily. Squeeze lemon over it and serve with, for example, boiled potatoes and vegetables. For me, it is above all the fish itself that is the thing. Haddock will probably always taste a bit Icelandic.

8. Mackerel in dill sauce – a taste from childhood

Of course, not all food memories come from trips abroad. Mackerel in dill sauce is one of my childhood favorites and a dish that, for me, is associated with the Swedish west coast. It may not be the most modern or Instagram-friendly fish dish in the world – but that doesn’t matter. Some flavors simply stick around.

You will need

• mackerel fillets
• butter
• cream
• plenty of dill
• salt and pepper
• lemon

Do the following

Fry the mackerel fillets gently in butter and season with salt and pepper. Pour in the cream and add plenty of chopped dill. Let everything simmer gently until the fish is done and the sauce has taken on some flavor. Squeeze some lemon over it and serve with boiled potatoes. Simple Swedish food – and for me a real nostalgic dish.

9. Perch in cream sauce – Peter's archipelago specialty

Last but not least, we come home to the archipelago. Perch is one of Peter's absolute favorite fish, and he is also really good at filleting it.

Anyone who has ever tried to make nice boneless perch fillets knows that it can take a little patience. But once the job is done, no special cooking is needed. Fresh perch is fantastic as it is.

READ MORE: Filleting perch - Peter's tips and best recipes

You will need

• perch fillets
• butter
• cream
• salt and pepper
• dill or parsley
• lemon

Do the following

Fry the perch fillets gently in butter. Season with salt and pepper. Pour in the cream and let the fish simmer gently in the sauce for a short while. Finish with dill or parsley and a little lemon. Serve with boiled potatoes. It doesn't have to be any more difficult than that – especially not when you have fine fish from the archipelago.

Fish on the go – and travel on your plate

It's fascinating how strongly flavours can be associated with places and memories. We only need to eat a certain tuna sandwich to think of Sliema. Haddock can take me back to my year in Iceland, while a Fischbrötchen makes us think of ports and coastal towns in northern Germany.

And then there are the flavors from home. The mackerel from childhood and Peter's perch from the archipelago. Maybe that's why we like to discover food when we travel. Part of the journey can come home with us – and reappear on the plate many years later.

READ MORE: Seafood Recipes – 9 Favorites from Our Travels and Our Kitchen