The old-fashioned and popular pastrami sandwich gets the star treatment with homemade rye bread, gruyere cheese and mustard.

Twist on a classic
This pastrami gruyere sandwich took me back a long time, to the years I lived in California, where I discovered wheat thins and graham crackers and ate pastrami for the first time.
It was served warm with chips and pickles, and I always had it on my way to San Francisco. It was so good that I remember it decades later.
Pastrami, in case you're not very familiar with it, is a meat product, usually beef brisket, that is brined for several days and then slowly cooked (or braised, really) to achieve a super tender, pull-apart piece of meat.
It's fantastic. Both the pastrami and the sandwich.
And a far cry from my other favorite, this meat sandwich with chimichurri.

Rye bread
For today's sandwich, I wanted a simple, straight-dough bread that could be made in a day. It's also great for toast and freezes well.
You can also use store-bought rye bread and make your life easier.
This is a solid bread with caraway and cumin seeds and uses the straight dough method, so you don't need ferments, sponges or overnight stays in the fridge.
Just a regular loaf of bread with the slight tang of rye which is enhanced by buttermilk.
I was apprehensive about the seeds in the pastrami and the rest of the ingredients, but somehow, this bread is perfect for this sandwich.

Kitchen Notes
- Organization: read the recipe first and ensure you have ingredients at the correct temperature, utensils and equipment needed, and enough workspace. This will make the process so much easier.
- Bread: I favor the homemade rye bread below or this oatmeal whole wheat sandwich bread. But any store-bought one you like will be perfect.
- Mustard: brown or spicy mustards are the best and the ones used in the original sandwich. I made it with purple mustard on occasion, a condiment that appeared years ago, and it was a really nice variation.
- Ratio: the amounts of each ingredient given below are an estimate. Adjust to your personal preference with more of this or less of that.
Related recipes you might like:
Let me know in the comments below if you made this recipe and loved it and if you had issues so we can troubleshoot together. I love to hear what you think, always. Thanks for being here. It's much appreciated.
You might also consider subscribing to our FREE email series 'Baking the Best' and our regular newsletter. Or connect via Facebook, Instagram, and Pinterest.

Pastrami Gruyere Rye Sandwich
Click the stars to Rate this Recipe!
Ingredients
For each sandwich:
- 2 slices rye bread, recipe below or use store-bought
- 5 ounces pastrami
- 3.5 ounces gruyere cheese, thinly sliced
- 1 tablespoon mustard, or more to taste
For the rye bread:
- 1 tablespoon dry yeast
- ¼ cup warm water
- 1 cup rye flour, finely milled
- 1 cup whole wheat flour, finely milled
- 2 teaspoons salt
- ¾ cup buttermilk, at room temperature
- 2 tablespoons malt syrup, or molasses
- 1 tablespoon honey
- 2 tablespoons sunflower oil, or other vegetable oil
- 2 teaspoons caraway seeds, crushed or coarsely ground
- 1 teaspoon fennel seeds, crushed or coarsely ground
- 1 cup bread flour, or all-purpose flour
Instructions
For each sandwich:
- Lightly toast 2 slices rye bread.
- Spread one side with 1 tablespoon mustard. Top with 3.5 ounces gruyere cheese, sliced and return for a few minutes to the oven until the cheese begins to melt.
- Arrange 5 ounces pastrami slices on top of the other bread slice.
- Top with the inverted slice with cheese.
For the bread:
- Grease one 9x5 inch (23x13cm) loaf pan. Set aside.
- In a small bowl mix 1 tablespoon dry yeast and ¼ cup warm water and let foam for a few minutes.
- In the bowl of the stand mixer, put 1 cup rye flour, 1 cup whole wheat flour, 2 teaspoons salt, ¾ cup buttermilk, 2 tablespoons malt syrup, 1 tablespoon honey, 2 tablespoons sunflower oiland yeast mixture. Mix with a wooden spoon until it integrates.
- Attach the dough hook and start mixing on medium-low speed until a shaggy dough is formed.
- Add 2 teaspoons caraway seeds, 1 teaspoon fennel seeds and 1 cup bread flour, a few tablespoons at a time.
- Beat for 6 to 8 minutes, until the dough is elastic but not too stiff. If it's too sticky add a few more tablespoons of bread flour but don't overdo it. It needs to retain some stickiness.
- Transfer dough to an oiled bowl, cover with plastic wrap, and let rise until doubled, about 1 hour. It can take more time depending on the temperature of your kitchen.
- On a lightly floured surface, pat the dough down, and then roll it tightly, pinching edges to seal.
- Place in the prepared pan, cover with a clean kitchen towel, and let rise again until doubled, about 1 to 1 ½ hours.
- About 20 minutes before baking, preheat oven to 375ºF (190ºC).
- Bake for 35 to 40 minutes, until golden brown and the bottom sounds hollow when tapped.
- Let cool completely on a wire rack before cutting.
Notes
Bread is adapted from an old version of the New Complete Book of Breads.
Jeanette T says
I had all of my ingredients out then realized that there was no salt listed. Is that an oversight or intentional? Thanks so much
Paula Montenegro says
Hi Jeanette, it does use salt, I added it. Apologies for that.
Jeanette T says
Thank you. I used bakers percentage of 2% which is 7.2 grams so Iโll be close. Iโll let you know how it comes out. Thanks so much
Cocoa and Lavender says
I can only imagine that this was the best sandwich ever! I love Palo Alto - there is a wonderful chocolatier there! It is one of my favorite places that my work takes me!
Andrea_TheKitchenLioness says
Paula, you made mustard too...only this time it has red wine...and you baked your own bread...quite an "ambitious" sandwich I must say. Gruyรจre is wonderful, of course, but we do not really get pastrami around here at all. What a Monday treat!
Laura Dembowski says
Love homemade bread! That sandwich looks incredible. The back story behind it is great too!
yummychunklet says
I'm salivating over your sandwich! Yum!
Kathy says
Iโm sitting here looking at that sandwich and wishing I could reach through the computer! Not only do I love your beautiful bread, but RED WINE MUSTARD sounds amazing!! I will be making that!
Heather Schmitt-Gonzalez says
First of all - YES! That is a fantastic book...I have it and dream of baking so many of the breads inside. This sandwich looks insanely delicious with that melty gruyere and the mustard...oh yes, my mouth is watering!
Abbe@This is How I Cook says
I am afraid I'm not a rye bread person but that mustard sounds intriguing. May have to add it to my mustard collection!
e / dig in says
your homemade rye looks delicious, paula. i can imagien it with a good wedge of cold creamy butter.
and i shall pass your red wine mustard recipe on to my mother - she is the condiment maker in our family!
Carol | a cup of mascarpone says
My goodness, Paula!!! You made your own bread, AND your own mustard!!! You. Are. Amazing!!! Rye, with seeds, is one of my favorite breads that carries such wonderful memories from childhood, weird, with my Italian heritage...so I really love rye! Great post!
Liz Berg says
I rarely have pastrami, either, but I love it! This looks like a healthier option to a corn beef sandwich...at least in my book! YUM!
Marissa | Pinch and Swirl says
This is just weird - I told Keith yesterday that I was craving a Reuben. Guess how many Reubens I've had, ever. Zero. Just the flavor combination sounds so good. This seems Reubenesque, but better. It's a sign! ๐ Definitely trying this sandwich...
Angie's Recipes says
I will have to try your red wine mustard. It sounds fabulous.
Inside a British Mum's Kitchen says
Oh yes please!!!
Mary x
Gloria Baker says
OMY I love pastrami and this look awesome!!
dentistvschef says
awesome, youve made it from scratch
Natalie G says
Wow that red wine mustard sounds fantastic! What a sandwich ๐
Deb says
My husband would adore the red wine mustard with pastrami! He worked in Palo Alto for six years, commuting four days a week from Salinas where we live. I'm happy to say those days are over. But that trip pales in comparison from your journey!
Alice @ Hip Foodie Mom says
Paula,
I love everything about this sandwich! And you made this rye bread yum! I will have to try this red wine mustard. . it sounds so intriguing! Although, we never seem to have leftover wine. ๐
And re: planes, I am the opposite. I have to eat and watch a movie or something but I know what you mean. It can get messy and then you have to get up and squeeze into the tiny lavatory!
Renee says
Best pastrami sandwich I've ever seen. Hands down.