Seafood Paella (On The Grill)

5 from 2 votes
Jump to Recipe

Sharing is caring!

Seafood Paella is a fantastic dish to cook for a small gathering or dinner party. It’s a one pot dish that has all the ingredients of an amazing feast, from hearty and aromatic rice, to a mix of seafoods and meats that please the palate. Our take on Paella is packed with fresh seafood and herbal flavors.

A pot of seafood paella with two glasses of rosé wine and a small bowl with lemon wedges

Paella is a dish that can instantly transform me to Spain. I remember distinctly the ginormous pan our group was served at a lunch I attended several years ago in the region of Murcia (south of Valencia where this dish has its origins). It was enough to feed over 25 people, and a meal that has remained in my memory since. It’s a dish I now love to make for friends back at home. Not only is its presence a show stopping centerpiece at any dinner table, it’s surprisingly an easy one pot dish to make and can easily be scaled down for a small family, or made in large quantities for a group dinner or event.

Paella can seem intimidating when you first look at a list of ingredients, but it’s actually quite easy to make and worth the effort. The flavors and aromatics from the saffron and chorizo are amazing together, and the steamed seafood balance out the rice for a bountiful, colorful, and festive meal. Add a little charcoal infused flavor from the grill and you have a great combination for seafood paella.

In this recipe we’re not using a paella pan. Instead we’re substituting for a pan most people already have in their kitchen, and we’re cooking this pot of deliciousness on the grill! No specially supplies needed.

What is Paella

Paella (a word that translates to “frying pan” in Valencian) originated in Valencia, Spain. It is a dish that began as a farmer and field hand dish, consisting of rice, stock, and meat, and whatever else was available to cook. Basically a one pot dish.

Today, Paella can take on a number of culinary flavors, from chicken, seafood, and even vegetarian. Saffron is a key ingredient that gives Paella that signature rich red color, and earthy and floral flavors, while other spices have been added over the centuries for unique flavor, like turmeric.

Depending on where you go in Spain the dish will present different regional variations, but the heart of the dish has humble origins.

For a flavor profile, paella is aromatic and the rice is cooked slightly al dente or even with some caramelization on the bottom of the pan for a crispy bite.

Seafood Paella Ingredients

Ingredients for seafood paella on a wood cutting board
  • Paella Rice – At its basic level, Paella is about stock and rice, specifically a short grain rice (the starchy small and round rice). There are Spanish varieties of rice that are great for a more authentic flavor but are often hard to find. If you can find a Spanish rice, use the same cooking methods as we describe below. In our case, we are using Arborio rice, and while it’s Italian, it’s also widely available and is a good substitute for the Spanish version.
  • Saffron – Our dish calls for Saffron, one of the most expensive spices in the world! It’s an incredibly aromatic spice to add to dishes and will give the rice the distinctive red color and floral and earthy deep flavor. A little will go a long way when making this dish. Just a pinch is needed here.
  • Chorizo – We are using a (pre-cooked) Spanish style chorizo for the dish. This adds a balance of savory and salty pork flavor. We prefer Spanish chorizo for this dish which has more paprika and earthy flavors, than it’s Mexican counterpart. However, each can be a good substitute. We’ve also used pre-cooked Italian sausage when we couldn’t find chorizo.
  • Seafood – We are adding three seafood elements into our seafood paella; mussels, cod, and shrimp in the shell. The shrimp in the shell is really for presentation, if you don’t want to have to pick the shell off when eating, then feel free to buy peeled and deveined shrimp (your kids will appreciate this).
  • Aromatics – The remainder of the ingredients are for aromatics and are meant to add subtle flavors to the dish, like softened red onions, red peppers, garlic, and crushed tomatoes. If you use canned tomatoes, be sure to discard the liquid so the liquid ratio is not too high.
  • Liquid – Chicken stock is a balanced flavor and provides the necessary liquid to reduce and soften the rice. You can also use seafood stock if you have access to it.

Cooking Supplies

Traditional Paella is cooked in a steel shallow and wide pan. The metal is important for cooking over fire. When making this seafood paella recipe, consider at minimum a 12-inch wide, shallow, stainless steel pan. The steel, versus it’s cast-iron cousin, does not retain the heat as efficiently and helps to prevent burning when cooking on the grill.

Cast Iron can be used (especially if that’s all you have), however it retains heat so well that it can burn the rice at the bottom as you simmer the stock and rice. So it is important to monitor your temperatures and cook over indirect when making Paella on the grill, especially with cast iron.

If you have the means and plan to make this dish often, then a Paella Pan is a good investment (as well as good BBQ gloves to hold it).

We do not recommend using a wok because the wok has a deep bowl and is not conducive to the liquids evenly cooking with the rice as the liquids incorporate.

When we started making paella we did not have a proper paella pan, and are just as happy as the results. So for this recipe we’re showing you how to make this classic dish without needing a specialty pan.

A large pan filled with seafood paella
A 12-inch stainless steel pan is the smallest dish we recommend for this recipe. If you have one, aim for 14 to 16-inches for these portions.

Preparation

Paella is more about the steps for cooking than actual preparation.

  1. Make sure that the shrimp and cod (or other white fish) are pre-seasoned with our seafood seasoning. This is going to add another layer of flavor to the overall dish.
  2. Clean the mussels of any barnacles and de-bear them. This removes any outside foreign flavor. Soak them for about 15 minutes in cold water prior to going into the pot. The time in water allows some of the grit inside the mussels to release into the water versus into your dish.
  3. Precut the onions, peppers, garlic, and chorizo so they’re ready to go into the pot.
  4. Grill the cod separately, on the side of your paella dish (see photos below). Then when it’s done cooking, cut into small, rough chunks to add to the dish towards the end.

How to Make Paella on the Grill

4 Step by step photos demonstrating how to make paella on the grill
  1. Prepare the grill for two-zone or indirect cooking. The indirect cooking prevents scorching the pan while you are simmering the rice. Place an empty large shallow pan (or paella pan) on the grill over indirect heat to warm up so it’s nice and warm when you are ready to start cooking.
  2. In a separate, medium-size sauce pan, bring the stock to a low simmer. Add the saffron, stir, and turn off heat. Continue to stir the saffron with the stock every few minutes before adding it to the rice. This allows the saffron to infuse the flavor and color into the stock.
  3. When the grill is at temperature add the butter, olive oil, onions, and peppers to the large pre-heated pan. Stir every few minutes, closing the lid of the grill between stirring. Stir to soften for about 10 minutes.
  4. At the same time, add the seasoned cod to the grill grates, outside the pot (you can also add lemons, directly to the grill grates, for grilled lemon garnish). The goal is to par cook the fish for some grill flavor.
  5. Add the garlic and chorizo chunks and stir to heat up, stirring, for about 2-4 minutes. The paprika and fat from the chorizo will add color and flavor. Next, add the rice.
  6. Stir rice for two minutes to incorporate the flavor and slightly toast the rice. Then add stock (including saffron in the stock), tomatoes, salt, and pepper, and stir to combine. Cover grill to bring heat back up. After 10 minutes stir (once), the liquid should be just starting to bubble at this point. Close the lid and let the liquid simmer and incorporate into the rice.
  7. After 10 additional minutes, add the mussels, shrimp, and cooked cod to the top of the rice mixture. If you want a crusty base, do not stir the rice at this point. Just gently pocket the fish into the dish. If you aren’t going for a crusty base, then feel free to stir.
  8. Cook an additional 5 – 7 minutes until the mussels open up and the shrimp is cooked through.
  9. Remove from heat, top with parsley, and serve with a squeeze of grilled lemon.
A pot of paella cooking on the grill

The Socarrat

Unlike the buttery and soft texture of risotto, Paella benefits from a slow caramelization of the rice at the base of the pan which gives a nice crunchy bite to the dish. This is called the Socarrat, and is normal. This is why we are sensitive to stirring the dish too much, and instead allowing the slow caramelization of the dish and a balanced ratio of liquid.

For our Seafood Paella it’s important that there is a fine balance of the Socarrat versus burning. So be sure to target 450 degrees F for the ambient temperature of the grill and to balance the liquids. If the pan is right over the heat source, it will burn.

If this flavor profile is not something you desire, than the easy way to manage the dish is to consistently stir it as the rice simmers.

Troubleshooting Seafood Paella

The two most common issues you may run into is the liquid cooking too quickly, or having too much liquid. Both are typically due to the ambient heat being too hot, or tool cool, for your grill and pan. So try to maintain around 450 degrees F in the cooker using indirect cooking.

  • Liquid Cooks too Quickly – Some grills may burn hotter, especially as you have your lid open while making the dish. Keep an extra cup of stock ready, and if the rice is not fully cooked before you add the seafood, then add the additional cup of stock (a half cup at a time).
  • Too Much Liquid – If the liquid is not cooking out enough, which can be caused by the moisture from the tomatoes and seafood, then increase the heat by 50 degrees. It may take a few extra minutes in each stage to allow the liquid to incorporate with the rice. It’s all about finding the right balance.

Modifications Based on Grill Types

For the Big Green Egg or Kamado Grill – We use the ConnvEGGtor plate to create the two zone cooking.

For a Kettle Grill – We use a standard two-zone method, using lump charcoal. Be sure the ambient temperature of the grill is at least 400 degrees with the lid on.

Gas Grill – If you have a three (or more) burner set up, light the outer burners so the center burner is off. Place the pan over the center burner so there is no direct heat. Be sure the ambient temperature of a gas grill is at least 450 degrees.

Pairing Wine with Seafood Paella

A grey plate with seafood paella and a glass of rosé wine next to it

You have quite a few options when it comes to pairing wine with seafood paella. I tend to lean towards rich earthy whites and rosé for this dish, but you can also reach for a red if that’s what you’re craving. A chilled fruity rosé is my favorite match. The fruity flavors are a solid match for the bright flavors of the dish. I love Spanish rosé for this, or southern French if you can’t find any from Spain. For white wine, stick with something a little earthy and rich, to balance out those earthy flavors from the sea and saffron. A barrel aged white (Chardonnay and Viognier work well) will balance out any smoky flavors from cooking on the grill.

For red, stick with something, light, fruity, and young. Reds tend to clash with certain seafoods, like as cod and mussels, so I would stick with a young Rioja, Gamay Noir, or lighter style Pinot Noir.

Want to save this recipe?
Just enter your email and get it sent to your inbox! Plus you’ll get new recipes from us every week!
Please enable JavaScript in your browser to complete this form.
Grilled Seafood Paella
5 from 2 votes

Seafood Paella Recipe (On the Grill)

This fragrant classic seafood paella recipe has sautéed onions and Spanish Chorizo with an aromatic saffron infused rice with seafood, all cooked on the grill. This one pot meal is amazing and is great for a small group of people.
Prep: 30 minutes
Cook: 40 minutes
Total: 1 hour 10 minutes
Servings: 8 people

Equipment

  • 12-inch steel pan (or larger) or 15-inch classic paella pot

Ingredients 

  • 1 pinch saffron
  • 4 cups chicken broth
  • 2 tablespoons unsalted butter
  • 2 tablespoons extra virgin olive oil
  • 1 ½ cups finely diced red onion, (one medium onion)
  • 1 red bell pepper, diced
  • 6 cloves garlic, finely diced
  • 8 ounces *Spanish Chorizo, sliced into 1/4 inch slices , (Spanish Chorizo is more paprika driven than a Mexican Chorizo. Use whichever you can find.)
  • 2 cups Arborio rice
  • 1 15-ounce can diced tomatoes, drained of excess liquid
  • ½ teaspoon kosher salt
  • ½ teaspoon coarse black pepper
  • 1 tablespoon seafood seasoning, (Use ½ tablespoon for cod, and ½ tablespoon for shrimp. Season the seafood prior to cooking.)
  • 1 pound mussels, (Remove the beards and clean the shells of barnacles. Also soak them for 15 minutes in water.)
  • 1 pound 16/20 count shrimp, seasoned
  • 1 pound cod (or other white fish), deboned and seasoned, (We used Ling Cod)
  • 1 lemon, sliced in half along the hemisphere
  • ¼ cup chopped fresh parsley

Instructions 

  • Preheat Grill – Prepare the grill for two-zone or indirect cooking. The indirect cooking prevents scorching the pan while you are simmering the rice. Place an empty large shallow pan (or paella pan) on the grill over indirect heat to warm up so it’s nice and warm when you are ready to start cooking.
  • Infuse Saffron – In a separate, medium-size sauce pan, bring the stock to a low simmer. Add the saffron, stir, and turn off heat. Continue to stir the saffron with the stock every few minutes before adding it to the rice. This allows the saffron to infuse the flavor and color into the stock.
  • Sauté Vegetables – When the grill is at temperature add the butter, olive oil, onions, and peppers to the large pre-heated pan. Stir every few minutes, closing the lid of the grill between stirring. Stir to soften for about 10 minutes.
    making paella on the grill
  • Grill Cod – Add the seasoned cod to the grill grates at any point, outside the pot (you can also add lemons, directly to the grill grates, for grilled lemon garnish). The goal is to par cook the fish for some grill flavor prior to steaming them.
  • Add Garlic and Chorizo – Add the garlic and chorizo chunks and stir to heat up, stirring, for about 2-4 minutes. The paprika and fat from the chorizo will add color and flavor. Next, add the rice.
    making paella on the grill
  • Add Stock – Stir rice for two minutes to incorporate the flavor and slightly toast the rice. Then add the saffron infused stock (including the saffron pieces), tomatoes, salt, and pepper, and stir to combine. Cover grill to bring heat back up. After 10 minutes stir (once), the liquid should be just starting to bubble at this point. Close the lid and let the liquid simmer and incorporate into the rice.
    making paella on the grill
  • Add Seafood – After 10 additional minutes of simmering, add the mussels, shrimp, and cooked cod to the top of the rice mixture. If you want a crusty base, do not stir the rice at this point. Just gently pocket the fish into the dish. If you aren’t going for a crusty base, then feel free to stir.
    making paella on the grill
  • Steam – Cook an additional 5 – 7 minutes until the mussels open up and the shrimp is cooked through.
  • Serve – Remove from heat, top with parsley, and serve with a squeeze of grilled lemon.

Notes

*Spanish Chorizo is pre-cooked. Make sure the sausage or chorizo you find is of the pre-cooked kind. 

Nutrition

Calories: 476kcal | Carbohydrates: 47g | Protein: 34g | Fat: 15g | Saturated Fat: 5g | Trans Fat: 1g | Cholesterol: 201mg | Sodium: 1473mg | Potassium: 624mg | Fiber: 3g | Sugar: 2g | Vitamin A: 902IU | Vitamin C: 45mg | Calcium: 132mg | Iron: 6mg

Nutrition information is automatically calculated, so should only be used as an approximation.

Additional Info

Prep Time: 30 minutes
Cook Time: 40 minutes
Total Time: 1 hour 10 minutes
Course: Entree
Cuisine: American, Spanish
Servings: 8 people
Calories: 476
Keyword: paella, paella recipe, seafood paella, seafood paella recipe
Like this recipe? Leave a comment below!

mary cressler headshot

Vindulge

About Mary


I'm Mary, a wine/food/travel writer, Certified Sommelier, mom of twins, former vegetarian turned BBQ fanatic, runner, founder of Vindulge, and author of Fire + Wine cookbook. Thanks for stopping by!

You May Also Like:

Leave a comment

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

Recipe Rating




This site uses Akismet to reduce spam. Learn how your comment data is processed.