Coyaba Restaurant Providenciales (Provo), Turks & Caicos IslandsReviewed March / April 2015

A photograph of Romantic tropical gardens, gazebo and under the stars dining at Coyaba, Providenciales (Provo), Turks and Caicos Islands. Romantic tropical gardens, gazebo and under the stars dining at Coyaba

By Mandy Rostance-Wolf
Photography By

Brandishing a distinctive and influential culinary style, Paul Newman, executive chef and owner of Coyaba, is in a category all his own. Coyaba is his personal and significant contribution to this island’s culinary industry. Many of the templates he has established over the years have set a benchmark for fine dining on Provo today. He set the bar and continues to raise it. Paul is the first to admit, “I’m still evolving … I always have.”

Several decades of living and working in many exotic locales have made Paul a leading authority when it comes to indigenous Caribbean ingredients like tropical fruits, spices, herbs and exotic seafood. Combining these Caribbean elements with European influences, he creates a contemporary and avant-garde ‘New World Cuisine’ with a menu that reads like a gastronomical bestseller.

A photograph of Chef Paul Newman’s fresh Grilled Wahoo, Providenciales (Provo), Turks and Caicos Islands. Chef Paul Newman’s fresh Grilled Wahoo

Set in a romantic and enchanting tropical garden, twinkling lights, lush foliage and gurgling fountains welcome you to relax and dine unhurriedly in the spacious open-air gazebo, or under nature’s canopy of dazzling stars. The emphasis is on making your dining experience unpretentious and relaxed, with a pleasurable degree of service, attention and professionalism, which was seamlessly executed this evening. Lizzie gracefully and elegantly hosted our table, and Sommelier Jeremy was conversant and happy to assist with wines.

Enjoy pre-dinner crudités as you peruse the Classic Signature Menu that features many revered and time-honoured dishes, in the company of the always enticing and innovative Daily Specials including a Soup, Slider and Pasta of the Day. And if that is not enough, prepare to be regaled with the evening’s ‘verbal’ specials—further gustatory delights that only serve to confound, beguile and bewilder diners already agog with anticipation.

A photograph of Coyaba’s legendary Lobster Thermidor, Grace Bay, Providenciales (Provo), Turks and Caicos Islands.Coyaba’s legendary Lobster Thermidor

At Coyaba every dining experience is a culinary adventure. To embark on this epicurean escapade, Chef Patrick prepared two amuse-bouches (literal translation: mouth amusers), each served on a Himalayan salt block. While the beautiful, pale pink block certainly adds to the presentation, placing food on its surface causes the block to sweat, infusing the food with lovely, salty flavours. The blocks can even be heated to sear food and are also used for curing.

First on the block, tender, melt-in-your mouth chunks of Tuna Sashimi encrusted with pink peppercorns, wasabi, and bamboo and soya flavoured sesame seeds, served with a coconut mango dipping sauce and a wakame seaweed salad. It was as stimulating to the eyes as it was to the palate.

Equally ‘amusing’ and deliciously crispy, Spicy Vegetable Curried Spring Rolls were stuffed with a lovely combination of butternut squash, zucchini, carrots, cilantro and green onions. A marvelous Tandoori spice blend engendered the perfect heat, while a mint-cucumber raita created a cooling and creamy contrast. An aromatic and lively Duck Horn Decoy Sauvignon Blanc complemented both dishes marvelously.

A photograph of Truffle Wild Mushroom Ravioli, Grace Bay, Providenciales (Provo), Turks and Caicos Islands. Truffle Wild Mushroom Ravioli

A palate provoking ‘shot’ of refreshing Gazpacho was a perfect pre-appetiser intermezzo.

This evening’s Slider of the Day was a luscious Lamb Slider. Tender, melt in your mouth lamb was smothered in a mint-cucumber raita sauce and sun-dried tomato pesto and served with a deep fried dill pickle. Yes, it’s actually called a ‘frickle.’ And that’s not the only thing Paul deep fries. Ginger, capers, and even banana caramel cheesecake all take on an entirely new, crispy and decadent dimension.

My Hibiscus Seared Carpaccio of Black Angus Beef Tenderloin was simply superb. Vibrant hues of garnet beef tenderloin were sliced so incredibly thin they verged on translucent. The meat simply melted on contact. This dish was flawlessly harmonised with a spectacular truffle vinaigrette, creamy avocado and generous shards of Parmigiano-Reggiano.

Served in a crunchy and edible noodle basket, Coconut Tempura Shrimp is a classic Signature Menu offering. While my fellow diner raved of the “wonderful flakey texture” of the coconut tempura that enveloped the moist and juicy shrimp, he found himself in somewhat of a condiment conundrum, wavering between the three delectable dipping sauces: Barceló honey rum, Teriyaki soy, and sweet and sour.

Bay Scallop Ceviche is the indisputable personal favourite of my favourite dining companion. This delicately divine ceviche is presented in three beautiful seashells with seaweed salad, siracha Marie Rose sauce, tobiko caviar, and crisp ginger. Based on her faraway and preoccupied demeanor you would think she was experiencing this dish for the first time. She momentarily paused to sigh and compliment the spicy ‘kick’ that seemed to filter down into the seaweed salad.

Another brief interlude featured Guava Sorbet, a delightful palate cleanser that was sweet and invigorating.

A photograph of The perfect dessert, Baked Apple Pie a la Mode for two at Coyaba Restaurant, Grace Bay, Providenciales (Provo), Turks and Caicos Islands.The perfect dessert, Baked Apple Pie a la Mode for two

Slow Braised Pork Osso Buccolettes is a bastion dish and a menu mainstay; to remove it would incite certain anarchy … beginning with my husband. Long, slow braising ensures that the meat falls off the bone, and infuses and saturates the pork with incredibly intense flavours. Served with gratin potatoes, apple fritter, and honey carrot silk, this dish was so succulent, with the operative word being succulent.

My fellow diner was swift and uncompromising in his entrée selection - the Truffle Wild Mushroom Ravioli. Slicing into the tender pockets revealed a savoury and succulent filling of wild mushrooms perfectly balanced with a bright tasting basil plum tomato sauce, sautéed fresh spinach, and pine nuts.

I was equally swift and uncompromising to be first to ‘score’ the Veal Osso Bucco Stuffed Jumbo Tortellinis – again. Marcona almonds, Stilton foam, sauté dasheen bush (a.k.a. callaloo) and a natural jus complete this unparalleled dish.

Leave it to Chef Paul to take Fish & Chips to new heights – or more aptly, depths. A fabulously crispy and light Turks Head beer batter envelopes chunks of fresh island Strawberry Grouper, with nouveau, original accoutrements like guava ketchup, sauce remoulade, minted green pea purée and the ultimate indulgence, white truffle fries.

A well-balanced and food-friendly 2012 Belle Glos Meiomi Pinot Noir with chocolate and berry nuances, paired wonderfully with our appetiser selections. We then progressed to a more complex, full-bodied 2010 Stag’s Leap Merlot. Earthy, with plenty of lush fruit and silky tannins, it complemented our entrée courses.

A photograph of Executive Chef and Owner Paul Newman at Coyaba Restaurant, Grace Bay, Providenciales (Provo), Turks and Caicos Islands.Executive Chef and Owner Paul Newman

I have repeatedly eulogised Paul’s genius to turn the ordinary into the extraordinary. His innovative and brilliant creations are only augmented by his unrestrained and seemingly boundless ability to consistently create a quality product. A serious chef, Paul also sports an affable and entertaining sense of humour. Ergo, the Millionaire’s Burger. A grilled Kobe short rib and sirloin beef patty topped with a foie gras medallion, on a toasted bun. Forget the lettuce, tomato and pickle and indulge in lobster hollandaise, guava ketchup and saffron mustard.

There are venerated classics, like Paul’s Lobster Thermidor. Chunks, and I mean chunks, of delicate and succulent sautéed lobster come together with a Dijon sherry mustard crème and three-cheese gratin, artistically served in the shell, with pasta ‘antennae.’ Don’t even get me started on the Deconstructed Beef Wellington.

Chef Paul’s Jerk Chicken Supreme won him the Iron Chef competition 2011, at the 14th Annual Hot & Spicy Food Festival in Toronto, a definitive and well-deserved ‘nod from abroad.’ Experience the original here, then perpetuate your own food fantasies at home. The recipe is on page 43 of the 2015 Providenciales Dining Guide.

From the sweet to the savoury, from specialty coffees to dessert martinis, from after dinner drinks to ports and cognacs, rums of the Caribbean and even an extensive cigar list, decadence is offered here in so many varieties, ensuring that conundrum will rear its head yet again.

I’m rarely at a loss for words – my husband will vouch for that – but it seems that I always leave a Coyaba dining experience absolutely speechless.

Related Topics