Spain on a Fork > All Recipes > Tapas > Spain´s BEST-KEPT Tapas Recipe | Potatoes with Garlic Shrimp & Aioli
All Recipes, Tapas / March 10, 2023

Spain´s BEST-KEPT Tapas Recipe | Potatoes with Garlic Shrimp & Aioli

These Spanish Potatoes with Garlic Shrimp & Aioli, known as Patatas Arrieras, are one of Spain´s best-kept tapas recipes. It´s a very unknown dish from the region Andalucía, but a dish everyone should know about. As it´s packed with flavors, easy to make and done in just 40 minutes.

Spanish Potatoes with Garlic Shrimp & Aioli
Serve this tapas dish as an appetizer, like they do in Andalucía or even as a main course. Next to a garden salad, crunchy baguette and a bottle of Spanish wine. Either way, the flavors promise to blow you away.

Spanish Potatoes with Garlic Shrimp & Aioli
For this recipe I peeled the potatoes, as that´s how they´re typically prepared. If you prefer, you can leave the skins on the potatoes. The shrimp I used I bought frozen and thawed out. Just to make things easier. But you can also use fresh shrimp if you like.

Spanish Potatoes with Garlic Shrimp & Aioli

TIPS & TRICKS to Make this Recipe: To bring this dish together, first fry the potatoes. While they are cooking, make the garlic mayo aioli and get the shrimp ready. Once the potatoes are cooked, use the same pan to cook the garlic shrimp.

Spanish Potatoes with Garlic Shrimp & Aioli

Key Ingredients & Cookware I used in this Recipe:

If you´re not already subscribed to my youtube channel, become a subscriber and click on the bell icon to be notified everytime I release a new video.

Support Spain on a Fork. Get your Spain on a Fork Apron and other awesome Merchandise here.
Spain on a Fork Apron
Your SUPPORT Helps Spain on a Fork Keep Going

Join Me on Patreon!
Spain on a Fork Patreon

Watch the Video Below on How to Make these Spanish Potatoes with Garlic Shrimp & Aioli

Spanish Potatoes with Garlic Shrimp & Aioli
5 from 1 vote

Spanish Potatoes with Garlic Shrimp & Aioli | Patatas Arrieras

Course Appetizer
Cuisine Spanish
Prep Time 15 minutes
Cook Time 30 minutes
Servings 4
Calories 484 kcal
Author Albert Bevia @ Spain on a Fork



  • 1 1/4 cups extra virgin olive oil 300 ml
  • 3 potatoes
  • pinch sea salt


  • 3 tbsp extra virgin olive oil 45 ml
  • 6 cloves garlic
  • 12 raw jumbo shrimp peeled & deveined
  • 1/2 tsp hot smoked Spanish paprika 2 grams
  • pinch sea salt
  • dash black pepper


  • 1/2 cup low fat mayonnaise 115 grams
  • 1 clove garlic
  • 1 tsp lemon juice 5 ml
  • 1 tbsp extra virgin olive oil 15 ml
  • pinch sea salt
  • dash black pepper


  • handful finely chopped fresh parsley



  1. Add the olive oil into a large fry pan and heat with a medium heat

  2. Meanwhile, slice the potatoes (peeled) into rounds that are a 1/4 inch (.625 cm) thick

  3. Add the sliced potatoes into the pan with the hot olive oil, mix every 3 to 4 minutes so all the potatoes evenly fry

  4. After about 25 minutes and the potatoes are golden fried, remove them from the fry pan and over a wire rack with paper towels underneath, season with sea salt

  5. Run the remaining olive oil in the pan through a fine sieve and into a pitcher to use on future recipes


  1. Add the mayonnaise into a bowl, finely grate in the clove of garlic, add the lemon juice, olive oil and season with sea salt & black pepper, whisk together until you get a creamy texture


  1. Thinly slice the cloves of garlic and pat the shrimp dry with paper towels, then season with sea salt & black pepper

  2. Using the same pan as the potatoes, heat it with a medium heat and add in 3 tbsp of the reserved olive oil from the potatoes

  3. After 1 minute add in the sliced garlic, mix with the olive oil

  4. Once the garlic is lightly sauteed, about 30 seconds to 1 minute, add in the shrimp, all in a single layer, cook the shrimp for 1 minute per side or until fully cooked through, then add in the hot smoked paprika, quickly mix together and remove from the heat


  1. Add the fried potatoes into a large serving dish, top off with the garlic mayo aioli and then the garlic shrimp, sprinkle with a generous portion of finely chopped fresh parsley, enjoy!

Recipe Notes

Get the Hot Smoked Spanish Paprika I used to make this Recipe

Nutrition Facts
Spanish Potatoes with Garlic Shrimp & Aioli | Patatas Arrieras
Amount Per Serving
Calories 484 Calories from Fat 315
% Daily Value*
Fat 35g54%
Saturated Fat 5g31%
Trans Fat 0.02g
Polyunsaturated Fat 7g
Monounsaturated Fat 22g
Cholesterol 80mg27%
Sodium 582mg25%
Potassium 777mg22%
Carbohydrates 33g11%
Fiber 4g17%
Sugar 2g2%
Protein 12g24%
Vitamin A 254IU5%
Vitamin C 34mg41%
Calcium 64mg6%
Iron 2mg11%
* Percent Daily Values are based on a 2000 calorie diet.

Disclosure: At Spain on a Fork, we offer affiliate links to help you find what you need to re-create our recipes. If you like what we do, you can support us through our chosen links, which earn us a commission, but you still pay the same price. Learn more here.


  1. Stephanie

    5 stars
    This was SO amazingly good!!! My husband and I inhaled it for dinner & I plan to make it again. He’s actually from Spain (the north) & had never had this dish. I can’t wait to try your other recipes, thank you!!!

    08 . Aug . 2023
    • Spain on a Fork

      So happy to hear that! Thanks for the comment 🙂 Much love

      08 . Aug . 2023
  2. Ramya

    Cant wait to make this soon for me for the shrimp can i use mushrooms and mayo can i use vegan mayo i never had spanish potatoes with garlic shrimp and aioli before perfect for my after office snacks love your recipes as always brightens up my day everyday after work

    10 . Mar . 2023
    • Spain on a Fork

      Sounds great Ramya! Thanks for the comment as always 🙂 Much love

      12 . Mar . 2023

Leave A Comment

Your email address will not be published. Required fields are marked *

Recipe Rating