The family-run restaurant, founded by Ben and Esi Masina, has gone from strength to strength, since 2009.
It first operated as caterers Season to Taste Catering Ltd, the parent company, which formed the foundations of its birth into an elegant upmarket restaurant in 2016.
The owners have moved into what once was, I believe, a Chinese buffet restaurant but the inside and out has been completely transformed to give it a modern, fresh feel.
We popped in on a lovely Sunday afternoon when the weather was still crisp but the sun was shining and everyone seemed to be in a good mood.
And because it was a Sunday, éKhaya, which sits just off the A461 in Tipton, had a very laid back atmosphere when my wife, Kelly, and four-year-old daughter, Annabelle, walked in.
It may be like that all the time for all we know.
But anyway, it's very open plan and we were seated in the corner, near the bar area, but it seemed very spacious and the sort of place where it could easily cater for more upbeat nights.
The venue stays open into the early hours on Fridays and Saturdays, with entertainment sometimes laid on too, and it was also clear some of the clientele regularly used the restaurant.
Whether it was the two men watching Spanish football with an iced bucket of beers, or the families all enjoying some food, drinks, laughter and merriment scattered through the venue. It felt welcoming.
The system works like this: you place your orders at the bar, but then the food and drinks are brought out to you with waiter service.
However, if you want to order an extra drink, you have to go back to the bar – that's how it worked the Sunday we arrived anyway, which was fine by us.
The hostess/waitress was very helpful because it was not always clear actually what we were ordering.
I wanted to try something 'authentic', so to speak, but wasn't sure what some of the starters and mains were.
Crispy Madora Amacimbi, which was listed as a 'flavour of Africa', was one example. And I was soon informed that was caterpillars.
Now, I've got nothing against caterpillars – not at this stage anyway, as I've never tried them – but I thought for a first visit to the venue it may be better to play it a little safer.
There were plenty of other options, such as sticky barbecue or lemon and herb chicken wings, spicy king prawns, garlic break, sharing platers, warm breads with olives and hummus, or chicken liver paté.
But I was determined to try something new, so in the end I went for éKhaya peri peri-style gizzards.
I had a rough idea what gizzards but the waitress confirmed it was like liver, kidneys, things like that, all served in a special sauce.
I'd only tried liver once before and it was horrible. A lot of people have told me since that when it's cooked correctly, it's delicious, so I gave it a go.
It also came served with choice hot sauce, mayo, ketchup, etc, but I thought a bit of kick would nice.
Kelly went for garlic and herb beef skewers, while Annabelle, who had ordered pasta with curly fries, had her fries as her starter.
Now it's time to explain the portions. We did wonder why there were so many takeaway boxes lying under one of the counters at first but we soon realised why.
They were huge. The starters, if you were not starving, could probably pass for a main, but they were both very nice.
The gizzards had a sort of chewiness I wasn't expecting but served in the peri peri sauce, and dunked in some of that hot sauce, it worked really well.
I'm still not sure that kind of meal is for me but éKhaya's version was easily the best I had ever tasted.
Kelly's beef skewers had been cooked very nicely, with the beef not too tough. Again, the subtle flavours brought the taste of the meat out nicely.
Kelly noted how the food was nice and authentic, agreed the portions were large and said the beef starter was cooked nicely with a right level of tangyness.
It wasn't too spicy and the cuts of the meat used meant there was some gristly bits, which may have been hard to chew at times but they added to the flavour.
We were given the option to have all our meals, starters and mains, served at the same – and it would have been nice, in a way, to have been surrounded by a feast of food – but we decided against it, and the staff were good enough to give us some time between courses to chat and enjoy a drink.
If you don't eat meat, there's probably not much point in going to éKhaya. Flavoured meats is definitely the recurring theme. But if you do, you should like there.
Grills included medium and large tilapia, marinated in a mixture of herbs and African exotic spices; grilled boerewors, which were Southern Africa sausages; roast beef chuck; and the éKhaya mixed grill, which could also be served as an 'ultimate' – now that sounded like a real challenge.
Again, there was plenty for all tastes with barbecue pork ribs, and16oz T-bone steaks and 8oz sirloin steaks.
In the end, I went for the medium tilapia, with a side order of savoury rice. All the sides looked delicious too and included things like jollof rice, rice in peanut sauce, plantain and sadza, which all sounded very exotic and tasty.
Kelly went for the grilled full baby chicken, which saw the meat marinated in garlic, lemon, herbs and a touch of peri-peri sauce.
The tilapia was really nice, had an almost jerk seasoning flavour and kick to it, but again with subtle differences.
There was a lovely selection of meats too, and I'm sure I detected some more of those gizzards, but it all combined into a nice, exotic-tasting mixed grill of sorts.
With the savoury rice added on top, it was like having a barbecue fresh from the beach served in a nice restaurant in Tipton.
The baby chicken was certainly not a small meal, as the title may suggest, and there was enough to take home for a meal in the week too.
But again it was cooked well, tasty lovely and the sauce was just the right consistency – not smothered all over the chicken, taking away from the taste of the meat.
Further options for those with a much smaller appetite included a Greek salad with olives and feta cheese
There was also an array of desserts, more traditionally British than African, for the sweet tooth but we were far too full for that.
One that did stand was the grilled-fruit ice cream sundaes, served with a choice of strawberry, pineapple or banana, but maybe that's one for another time.
The restaurant is closed Mondays, open 5pm to 11.30pm Tuesday to Thursday, 5pm to 2am Fridays, 2pm to 2am Saturdays and, 2pm to midnight on Sundays.