Nom Nom Paleo

What to Order When Your Non-Paleo Friends Wanna Go Get Pizza: Matteo’s Pizzeria and Italian Restaurant (Wailea, HI)

Pin It

We are currently in Maui with our best friends, who happen to eat decidedly non-Paleo.  They are some of our favorite people in the world and the thing we love to do the most is eat out together.  Now that Fitbomb and I have changed our diet, eating out with them is not as simple as it used to be.  It’s hard to share everything like we did in the past and choosing a restaurant to eat at is more complicated because they LOVE Italian.  I don’t WANT to eat pasta and pizza but I still crave them sometimes. Especially if someone is oooohing and aaaaaaahing across the table from me while enjoying a bitchin’ dish of papparadelle with pork sugo at Delfina.   But I digress.

Besides Sansei, the only other restaurant our friends wanted to try in Maui was Matteo’s Pizzeria and Italian Restaurant in Wailea.  Again, since I’ve been a total food dictator when it comes to choosing where to eat this week, I relented and we dined at this pizzeria today after our morning trip to the Maui Ocean Center.

WTF did Fitbomb and I eat? 

Antipasto Platter with salumi, mixed greens, olives, and a mini Caprese salad:


Beef carpaccio with mixed greens, capers, and a lemon dressing:


House salad with added chicken:


House salad with added shrimp:


The food was fresh, delicious, and reasonably priced and you have a beautiful view of the ocean and golf course when you dine out on the patio.  I was glad that the salads and apps were really well-composed and carefully prepared —  and not some half-assed concessions for non-pizza eating folks.  See?  You can eat something filling and delicious and decidedly non-carby at pizza place!

Yes, A Tourist Trap Can Be Tasty And A Good Deal: Sansei Seafood Restaurant and Sushi Bar(Lahaina, HI)

Pin It

I was not looking forward to dinner at Sansei because our dinner there was really disappointing last year.  We ordered all their “signature” dishes and it was a bunch of crazy-ass fried cream cheese filled sushi rolls or dishes topped with sickly sweet sauces.  Icky. 

Our friends really wanted to eat here this week so I relented and reluctantly agreed to go.  I’ve been dictating where we’ve all been eating this vacay, so I suppose it was time I let someone else have a say.  And boy, was I glad I did.

This time, we steered away from the stuff that was noted as crowd pleasers and simply chose items that looked delicious and not overly complicated.  Here’s what we had:

Cajun seared white tuna sashimi with shaved Maui onion, red jalapeno and Yukke sauce:


Roasted Japanese eggplant with sweet miso-sake sauce:


Grilled Upcountry shiitake mushrooms with tangy soy-ponzu sauce:


Ahi tataki salad:


“Kenny G”: thinly sliced fresh sashimi grade shiromi with shiso, minced garlic, and masago in a tangy ponzu vinaigrette:


Delicious but what’s the deal with the name?  How is this a homage to the easy listening smooth jazz King?

Shichimi Seared Fresh Atlantic Salmon and Tiger Prawn served with asparagus, shiitake mushrooms, and soy butter sauce:


The salmon (which wasn’t local) was a tad over-cooked but the soy butter sauce was pretty amazing.

If any of you are interested in totally blowing your Paleo diet, order the tempura fried ice cream.  It’s vanilla ice cream wrapped in buttery pound cake, rolled in roasted macadamia nuts, flash-fried and served with chocolate sauce and whipped cream. 


This dessert is the sole reason our friend wanted to eat here.  It was not cheat-worthy in my book so I abstained.

Our meal was great and it cost HALF of what we paid the night before at Mama’s Fish House.  The fish here is super fresh and I definitely preferred the raw preparations to the cooked ones.  If you order before 6 pm, your bill is 25% off – so go be like an old lady and come in early!

It’s Déjà vu All Over Again, Part 2: Star Noodle (Lahaina, HI)

Pin It

No, we didn’t go to Mala again (we’re going for brunch this weekend) but we made a second appearance at Star Noodle.  Hey, pickings are slim here in Maui! So if you like a place, you should stick with it.  Life’s too short to waste a meal on something shitty. 

Today for lunch we ordered the following items:

Pan roasted local mushrooms:


Mmmmmm.  Umami goodness.   I liked this mushroom dish better than the similar one we ate at Mala the other day.

Special of the day: balsamic marinated grilled beef over local greens:


The beef was well-seasoned and served rare – just the way I like it.  The dressing also had a nice kick to it.

Garlic steak served sizzling with onions and scallions:


This steak was tasty but a tad over-cooked for my taste.  Fitbomb also found it a bit too sweet.

All in all, the food was nom nom-approved and it’s not just good for Maui —  I wish this place was located back where we live!   However, like all Asian places, it’s hard to eat truly Paleo at Star Noodle because there’s sugar, cornstarch, soy, etc. in almost everything even when you are avoiding the obvious carb-y things like noodles, rice, and dessert.   But I’m on vacation so eff all that stuff!

Dining Out Paleo: Mama’s Fish House (Paia, HI)

Pin It

Okay, I’d heard about Mama’s Fish House for a long fricking time but I always resisted coming here. Apparently, the fish was super fresh, the prices sky high, and the setting was old school Hawaiian. I also knew that it was a total tourist trap and I was skeptical about going to such a popular place. But can 580+ Yelpers be wrong? Well, my curiosity got the best of me and I booked us a table here tonight.

What did we eat? Our first taste was a freebie shot glass filled with tomato ginger bisque:

My appetizer was Ono marinated in coconut milk and lime, Tahitian style. You know how I love my coconut.

Fitbomb ordered the blue prawns in Tahitian vanilla beans and coconut milk sauce:

These prawns were super tasty. Maybe because they were coconut-y.

I was going to order their signature dish, macadamia nut crusted mahi mahi stuffed with lobster, crab, and Maui onion, but the server informed me that it wasn’t gluten free. Instead, she steered towards the Lehi fish that could be served gluten free. The Lehi fish was sautéed with tomatoes, white wine, garlic, and capers. I subbed out the lemongrass rice pilaf for some mixed vegetables.

My dish was fine but not mind blowing and there were some bitter zucchini in my mixed veggies.

Fitbomb ordered the Mahi Mahi Hawaiian style which came with a coconut butter sauce, Kalua pig, grilled Hana banana, sweet potato, star fruit, and poi:

Again, it was good but not $40+ good.

At the end of the meal, we got some free haupia (coconut jello):

What’s my verdict? It’s tasty and tiki-tastic but too damn expensive. I liked the Hawaiian theme, the friendly service,and the beautiful postcard views of the Pacific. However, it’s waaaaaaaaaaaaaaaay over-priced, an hour drive from where we were staying, and maybe a little too kitschy. Plus, I like my food prepared more simply. If you have a super fresh fish caught within 24 hours, why is it necessary to drench it with a thick, heavy ass sauce? Would we return? Fitbomb says “NO!” but I say maybe. It appeals to a wide swath of the population for a reason so it’s a good place to take grandparents, picky eaters, kids, etc. if you’re willing to pay through your nose. But you better be willing to treat them, or you’ll be in the doghouse.

Paleo Take Out: The Fish Market Maui (Lahaina, HI)

Pin It

After a leisurely morning at the beach making sand castles with the kids and snorkeling in the ocean, we just wanted to get some take out for lunch to eat at our digs.  We called up one of our old standbys, The Fish Market Maui in Honokowai and our order was ready to pick up in 10 minutes. 

The Fish Market Maui is both a fish market and a sandwich place and the food is great and reasonable for Maui.  Unfortunately, up until this visit, we’d only ordered the sammies and weren’t sure we could get anything here that was Paleo-friendly.  Thankfully, we were wrong.

I ordered the house salad with added grilled ahi (hold the croutons):


The salad greens were really crisp and fresh and the ahi was tasty but a bit more well-done than I like. I’d definitely get this again but with shrimp as my protein because my friend’s Caesar with shrimp had some big ass poached shrimp (not shrimpy shrimps). 

Fitbomb got the taco platter with Cajun mahi, Cajun shrimp, and Kahlua pork (3 different tacos):


We requested no tortillas but that was too difficult for the order taker so Fitbomb just ate around them.  He topped the tacos with guacamole we had purchased earlier today from the Farmers Market Maui. His favorite filling was the Kahlua pork so he’ll just get three porcine tacos next time.

The food at Fish Market Maui is fresh and tasty.  Plus, you can get their “Fresh Catch Card” where you buy seven items and you get your 8th free.  Since we had a completed card from last year, we got the tacos for free and we are two away from a freebie on the new card (we ordered some non-Paleo items for our friends and kids).

How the hell is Cool Cat Cafe voted the best burger in Maui 5 years in a row?  We came here for dinner tonight and I ordered a Jailhouse Rock (“juicy” burger served with sauteed mushrooms, grilled onions, and jack cheese) with no bun and a side salad.  So not worth it. My patty was overcooked and overpriced and the cheese wasn’t fully melted on top.  I hate that! Plus, you have to walk through all the touristy bullshit that is Lahaina Town to get here.  On another note, you do get served by cute and tatted Madden brothers lookalikes so I guess that’s a small plus in its favor. 

How the hell is Cool Cat Cafe voted the best burger in Maui 5 years in a row?  We came here for dinner tonight and I ordered a Jailhouse Rock (“juicy” burger served with sauteed mushrooms, grilled onions, and jack cheese) with no bun and a side salad.  So not worth it. My patty was overcooked and overpriced and the cheese wasn’t fully melted on top.  I hate that! Plus, you have to walk through all the touristy bullshit that is Lahaina Town to get here.  On another note, you do get served by cute and tatted Madden brothers lookalikes so I guess that’s a small plus in its favor. 

It’s Déjà Vu All Over Again : Another Lunch at Mala Ocean Tavern (Lahaina, HI)

Pin It

I knew we’d be back but I didn’t think it would be within 24 hours.   What can I say? We love Mala!  I tried not to order the same stuff as last time but we had to get another order of Brussels sprouts because they’re damn good. 

(To clarify, when I say that I’m eating Paleo when dining out I’m just trying to avoid grains, starches, and refined sugars.  I know that most restaurants use sugar, starches, and soy in their marinades and sauces but I just pretend I don’t know.)

Here’s what we ate at lunch today:

Cucumber salad with furikake:


Stir fried Brussels sprouts with sesame seeds, fresh mint, and crispy wontons (we ate around the wontons):


Ahi Burger (house made) with romaine, tomato, tartar sauce, and fries.  I asked them to hold the bun and my kids ate my fries.  Bad paleo mommy!


Avalon seared sashimi with spicy shiitake ginger sauce:


I have to admit that  the sashimi was not one of my favorite dishes.  I expected it to be more Japanese-y instead of Chinese-y.  Plus, there was a huge dollop of mashed potatoes on my plate that wasn’t advertised on the menu.  WTF?  Who pairs sashimi with mashed potatoes?  I forgive you, Mala, but it better not happen again. 

Who am I kidding?  We’ll probably be back in the next few days.

Can You Eat Paleo At A Place Named Star Noodle (Lahaina, HI)?

Pin It

Uh, yeah.

This place may supersede Mala Ocean Tavern as one of my favorite places to eat on Maui. It’s my new crush, no doubt.  Hubs likes that it’s down the street from the Crossfit affiliate he’s been visiting.  I like that it’s at the end of a windy road in an industrial part of Lahaina and our friends thought we were leading them to a quiet, deserted spot so they would get “lost” and we’d have our lodging all to ourselves. Heh heh.

Star Noodle is a casual and lively pan-Asian place that serves Asian shared small plates and different noodle dishes.  I normally dislike fusion places but Star Noodle is different in that the food is authentic and tasty.  Like most places on the island, this place is kid-friendly and they take reservations if your party is 5 and larger.  Plus, the food is affordable for Maui.

Here’s what we ordered for dinner last night:

Ahi Avo with lemon pressed olive oil, sambal, usukuchi:

Star Kim Chee with won bok cabbage, ginger, and garlic:

Pohole Salad with Hana fiddle head fern, Maui onion, ebi, and kombu:

Steamed Pork Buns with pressed pork, hoisin, shiitake, and cucumber: 

(In case you’re wondering, we didn’t eat the bun.)

Chicken Yakitori with teriyaki glaze, scallion, and sesame seeds:

Seared Scallops and Asparagus with yuzu miso vinaigrette:

Rib Eye served sizzling with Makawao mushrooms and negi:

Here’s a worthwhile cheat: homemade malasadas!