• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
  • Skip to footer
  • Paleo Recipes
    • Recipe Index
    • All Recipes
    • Instant Pot® Recipe Roundup
    • Paleo Packed Lunch Roundup
    • Whole30® Recipe Roundup
  • My Cookbooks
    • Nom Nom Paleo: Let’s Go!
    • Ready or Not!
    • Nom Nom Paleo: Food for Humans
  • Spice Blends
  • Shop
  • Events
  • Paleo Meal Plans
  • About
    • What’s Paleo?
    • About Michelle Tam
    • Nom Nom Paleo in the News

Nom Nom Paleo®

Paleo recipes and more from New York Times bestselling cookbook author Michelle Tam!

  • Email
  • Facebook
  • Instagram
  • LinkedIn
  • Pinterest
  • Twitter
Home » Blog » Recipes » St. Paul Sandwich (Paleo, Low Carb, Gluten Free)

St. Paul Sandwich (Paleo, Low Carb, Gluten Free)

Jump to Recipe Jump to Video Print Recipe

This St. Paul Sandwich is a paleo, low carb, and gluten-free version of the midwestern Chinese-American classic! You can assemble this sandwich in minutes if you already have some Egg Foo Young patties in the fridge!

Someone holding a paleo and gluten-free St. Paul Sandwich.

This dish represents me as a sandwich—an umami-packed, paleo-friendly Chinese American leftover makeover!

What is a St. Paul Sandwich?

A St. Paul sandwich is a midwestern Chinese-American classic: golden-brown egg foo young patties and pickles tucked in-between two pieces of white bread slathered with mayonnaise. Its origins can be traced back to Steven Yuen, the former owner of Park Chop Suey in Lafayette Square near downtown St. Louis, Missouri. Yes, you heard that right: ST. LOUIS. Although this sandwich first gained popularity in St. Louis, the sandwich is allegedly named after Yuen’s hometown of St. Paul, Minnesota!

Someone holding two halves of a St. Paul sandwich with gluten-free and paleo-friendly ingredients.

How is this sandwich Paleo?

In this healthier St. Paul sandwich, I’ve cut out the grains in the bread and egg patties, and added paleo-friendly condiments like Quick Pickled Red Onions and a spicy sriracha mayonnaise to amp up the flavors!

Leftover Makeover!

I love leftover makeovers because you can easily and quickly transform last night’s meal into something new and exciting. St. Paul sandwiches are one of the best examples of a leftover makeover—two times over!

My Egg Foo Young recipe is already a leftover makeover because you can fill the egg-y patties with leftover protein and vegetables. The next day, you can tuck leftover Egg Foo Young patties into these tasty sandwiches! Voilà!

Adding quick pickled onions on a paleo and gluten-free St. Paul sandwich.

I always make a double-batch of Egg Foo Young patties so I can use the leftovers to make St. Paul Sandwiches. When you’re hangry, you can assemble one in just a few minutes if you have all the ingredients on hand!

What Type of Paleo Bread Can You Use?

Luckily, paleo-friendly grain-free bread is not so hard to find these days! There are lots of great paleo sandwich bread recipes online, including this one by Danielle Walker. You can also buy a terrific paleo sandwich bread mix from Legit Bread Company. Too lazy to bake? You can buy fabulous paleo-and keto-friendly loaves from Misfits Bakehouse! They ship nationwide and you can order them here.

Guinness World Records Title!

On August 6, 2020, I helped set a Guinness Worlds Record title with this sandwich! I joined Al Roker alongside chefs from around the country in this year’s Rokerthon: Al’s Great American Sandwich Relay to break a new Guinness World Records record for the most sandwiches consecutively assembled live!

You can watch the record setting sandwich relay by clicking here. Skip to the 2:00:40 mark to see me assembling my St. Paul sandwich!

Time to Make St. Paul Sandwiches!

Makes 4 sandwiches

Ingredients:

  • 8 Egg Foo Young patties
  • ½ batch Quick Pickled Red Onions
  • ¼ cup Paleo mayonnaise (store-bought is fine!)
  • ¼ cup Whole30 Sriracha
  • 8 slices Paleo grain-free bread (see note above for recommendations)
  • 8 thin tomato slices
  • 4 leaves Romaine or butter lettuce

Equipment:

  • All of my recommended kitchen tools are listed here.

Method:

Go grab some Egg Foo Young patties and your jar of Quick Pickled Red Onions! You can heat the patties in a toaster oven or air fryer at 325°F for 5 minutes or until warmed through. (You can also assemble the sandwiches with cold Egg Foo Young, too!)

Four paleo egg foo young patties on a white plate.

In a small bowl, whisk together the mayonnaise and sriracha and slather the sriracha mayonnaise on one side of each piece of bread.

A knife is spreading sriracha mayonnaise on a slice of gluten-free and paleo sandwich bread.

Pile each sandwich with two paleo Egg Foo Young patties, two tomato slices, a handful of Quick Pickled Red Onions, and a lettuce leaf.

Adding a piece of lettuce on a paleo St. Paul sandwich.

Top the remaining pieces of bread on top of the four sandwiches.

Two hands topping a paleo and gluten free St. Paul sandwich with a slice of grain-free bread.

Slice each St. Paul sandwich in half and enjoy!

A closeup shot of someone holding a paleo St. Paul sandwich that has been sliced in half.


Looking for more recipe ideas? Head on over to my Recipe Index. You’ll also find exclusive recipes on my iPhone and iPad app, and in my cookbooks, Nom Nom Paleo: Food for Humans (Andrews McMeel Publishing 2013), Ready or Not! (Andrews McMeel Publishing 2017), and Nom Nom Paleo: Let’s Go! (Andrews McMeel Publishing 2021).


 PRINTER-FRIENDLY RECIPE CARD

A closeup shot of someone holding a paleo St. Paul sandwich that has been sliced in half.
Print Recipe
5 from 4 votes

St. Paul Sandwich (Paleo, Low Carb, Gluten Free)

This St. Paul Sandwich is a paleo, low carb, and gluten-free version of the midwestern Chinese-American classic! You can assemble this sandwich in minutes if you already have some Egg Foo Young patties in the fridge!
Prep Time5 mins
Cook Time5 mins
Course: Lunch
Cuisine: Chinese American
Keyword: gluten-free, low carb, nom nom paleo, nomnompaleo, paleo
Servings: 4
Calories: 540kcal
Author: Michelle Tam

Ingredients

  • 8 Egg Foo Young patties
  • ¼ cup Quick Pickled Red Onions
  • ¼ cup paleo mayonnaise or store-bought paleo mayonnaise
  • ¼ cup Whole30 Sriracha
  • 8 slices Paleo sandwich bread see post for recommendations
  • 8 slices tomato
  • 4 leaves Romaine lettuce or butter lettuce
US Customary - Metric

Instructions 

  • Go grab some Egg Foo Young patties and your jar of Quick Pickled Red Onions! You can heat the patties in a toaster oven or air fryer at 325°F for 5 minutes or until warmed through. (You can also assemble the sandwiches with cold Egg Foo Young, too!)
  • In a small bowl, whisk together the mayonnaise and sriracha and slather the sriracha mayonnaise on one side of each piece of bread.
  • Pile each sandwich with two paleo Egg Foo Young patties, two tomato slices, a handful of Quick Pickled Red Onions, and a lettuce leaf.
  • Top the remaining pieces of bread on top of the four sandwiches. Slice each St. Paul sandwich in half and enjoy!

Video

Notes

There are lots of great paleo sandwich bread recipes online, including this one by Danielle Walker. You can also buy a terrific paleo sandwich bread mix from Legit Bread Company. Too lazy to bake? You can buy fabulous paleo-and keto-friendly loaves from Misfits Bakehouse! They ship nationwide and you can order them here.
Tried this recipe?Mention @nomnompaleo or tag #nomnompaleo!

Nutrition

Calories: 540kcal | Carbohydrates: 33g | Protein: 21g | Fat: 24g | Fiber: 11g
18

Thrive Market   LunchBots   Real Plans

Reader Interactions

Comments

  1. VSM says

    August 11, 2020 at 2:30 pm

    Congratulations! I actually just finished a tomato sandwich for lunch! I’m not much of a sandwich eater, but when the tomatoes are fresh out of the garden I can’t pass it up! I found a recipe a few years ago (but I’m not sure where…) that only takes Cashew Butter, eggs, olive oil, salt, baking soda, and vinegar–I make a loaf and it freezes beautifully, so when ever the sandwich urge hits me, I’m ready with the toaster. Danielle Walker has wonderful recipes too! Thanks for always being an inspiration in my kitchen!

    Reply
  2. Taka @gingerpies says

    August 12, 2020 at 3:24 pm

    I love this sandwich and today I made two of them, one for my son and the other one for me. I followed your instructions in this article. Although my son is not a sandwich lover, today he fell in love with this type of sandwich. Thank you.

    Reply
  3. Into the FIRE says

    August 17, 2020 at 4:57 am

    This sandwich looks delicious! I might try making this one day. Thank you so much for sharing!

    Reply
  4. mare says

    August 30, 2020 at 10:14 pm

    michelle- do you find danielle’s bread to be overly “coconutty?”
    thank you,
    mari

    Reply
    • Michelle Tam says

      August 31, 2020 at 5:12 pm

      Not especially! I don’t expect paleo bread to taste identical to wheat bread because it is mosty made of nuts, coconut, and eggs.

      Reply

Leave a Reply Cancel reply

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

Recipe Rating




Logged in as . Log out? Required fields are marked *

Primary Sidebar

Archives

About Nom Nom Paleo Nom Nom Paleo Cookbooks Nom Nom Paleo App Nom Nom Paleo Spices
  • Email
  • Facebook
  • Instagram
  • LinkedIn
  • Pinterest
  • RSS
  • Twitter
  • YouTube

Popular Posts

  • An overhead shot of a paleo and Whole30 Green Goddess Cobb Salad Panera copycat. Panera Green Goddess Salad (Whole30, Keto, Paleo)
  • A hand is holding a mason jar filled with paleo, vegan, and Whole30 Green Goddess Dressing. Green Goddess Dressing (Vegan, Whole30, Keto, Nut Free)
  • An overhead shot of a frying pan filled with Egg Roll In A Bowl (also known as Potsticker Stir-Fry), a keto, paleo, and Whole30 one-pan meal. Egg Roll in a Bowl (Keto, Whole30, Gluten Free)
  • An overhead shot of crispy air fryer chicken thighs in an open air fryer basket. The Best Air Fryer Chicken Thighs: Cracklin’ Chicken!

Footer

COPYRIGHT© NOM NOM PALEO LLC. All rights reserved. The content on this website may not be copied or reproduced in any manner whatsoever without prior written permission.

HOME  •  PRIVACY POLICY  •  CONTACT

Copyright © 2023