The Russian side went into the encounter in good form, having won all seven of their home matches in the tournament so far this season.
However, Alan Pardew's Newcastle managed to halt that run of results by holding their hosts to a 0-0 draw ahead of next week's second leg on Tyneside.
You can find out how the match unfolded with our minute-by-minute commentary below.
4.01pmAfternoon all. Don't you just love the Europa League on a Thursday? Football starts at around 5pm and goes right through the evening. First up we've got some English interest as Newcastle United make the long old trip to Moscow to take on Anzhi Makhachkala.
4.03pmBefore we get into all the facts, figures and pre-match chat surrounding this tie, the team news from the Luzhniki Stadium has just been released. Let's start with the Magpies...
4.07pmWell, it looks as though Newcastle manager Alan Pardew believes that tonight's encounter will be a tough one. The visitors will begin the match without a recognised striker, with the main attacking role handed to Hatem Ben Arfa, who has only recently returned to the fold following a muscular injury. Full-back Danny Simpson and midfielder Vurnon Anita also start.
4.11pmThere are couple of names in that Anzhi lineup that Premier League fans are bound to recognise. Former Arsenal, Chelsea and Portsmouth midfielder Lassana Diarra has been included, as has Yuri Zhirkov, who also had a stint with Chelsea. Brazilian playmaker Willian and ex Barcelona frontman Samuel Eto'o start as well.
4.14pmCome on then - hands up - what do you know about Anzhi? The answer is probably quite a lot these days actually. As their starting lineup shows, they now have a squad packed with some big names and a coach to match. After all, Guus Hiddink has managed some of the biggest names in the business.
4.18pmHaving said all that, despite all the funds that billionaire Suleyman Kerimov has pumped into the club, they have won very little. Actually, "very little" is being kind. No silverware has been won at all and according to reports, the owner is keen for Hiddink to deliver the Europa League trophy this season. No pressure then!
4.21pmIf their form so far this season is anything to go by, this could be the year as far as Anzhi are concerned. They have won all seven of their home matches in the Europa League and qualified through a group that included names such as Liverpool and Udinese. They've also lost just two matches in the Russian League and currently sit second behind CSKA Moscow.
4.25pmWith all that in mind, it looks a pretty daunting trip for Pardew's players. It would be fair to say that they won't take much confidence from their away form so far this year either. In the Premier League, they have won just once on their travels, collecting eight points from a possible 42. Meanwhile, they've also emerged victorious just once from four outings.
4.28pmSo what has Pardew had to say about this match in recent days? While many see this competition as a distraction, the Newcastle manager has insisted that having got this far, he would like his side to go all the way.
"It would be massive if we could beat [Anzhi] because they are a really strong side," he told ITV Sport. "It's really now down to where every team left in that Europa League now is focusing on it probably as their primary objective.
"I can't think of too many clubs in it for whom it's not at the top of their agenda, so there's now a real focus on that competition."
4.32pmMeanwhile, despite the statistics and facts suggesting otherwise, Pardew's opposite number Hiddink is expecting that his team will have their work cut out against the Premier League outfit.
"We are going to have another very interesting and very tough contest against a team who reinforced themselves in the past weeks dramatically in a positive way," he told reporters.
4.36pmOne factor that is likely to have an impact on proceedings is the plastic pitch inside the Luzhniki Stadium. Those type of pitches are known to be unpredictable, which doesn't always suit those outfits that like to play passing football. If Newcastle are to collect a positive result here, they will have to adapt to the surroundings quickly.
4.39pmWhy the Luzhniki Stadium in Moscow anyway? After all, 1,000 miles separate the city of Makhachkala and the Russian capital. The problem is that Anzhi's 15,200-seat Dynamo Stadium is not up to UEFA standards when it comes to hosting a European match. As a result, Anzhi play most of their Europa matches in Moscow. So it is not only the Newcastle fans that will have to make a lengthy trip to see their side in action today!
4.41pmIn fact, a quick search shows that the Geordie faithful have only had to travel an extra 500 miles than their Russian counterparts for the match. It gives you the feeling that it could be a rather empty Luzhniki Stadium, unless this encounter captures the imagination of some neutrals.
4.46pmIt actually looks as though that the Anzhi players do not have too much to do with Makhachkala as a city. The players live and train in Moscow, with a large reason for that being the number of conflicts that are currently going on in the Dagestan area. It seems as though it is best all round that they play some of their matches in Moscow.
4.51pmWhile a lot of what has gone before this post may have not given Newcastle much chance of winning this match - fear not fans of the Black and Whites! The last time you came up against Guus Hiddink in a European competition, you won. That was back in 2004 when the Europa League was known as the UEFA Cup and Newcastle ran out 3-2 winners on aggregate against PSV Eindhoven. Clutching at straws? We shall see.
4.55pmRight then, here come the players into was is a predictably rather empty stadium. It looks extremely cold in Moscow today and most of the players on show are kitted in gloves. I bet some wish they could wear a hat and scarf as well!
1 minHere we go then - Newcastle, kicking from left to right, get this final 16 tie off and running...
4 minA quick note on the attendance. The Luzhniki Stadium can hold up to 78,000 spectators, but officials reckon that just 12,000 are present this afternoon. So far they have seen very little happen on the pitch, with Newcastle looking the brighter of the two teams.
7 minPositive start from Rob Elliot in the Newcastle goal. Willian's free kick took a wicked deflection and flew up into the air, but the keeper was brave and collected at the first attempt. It is likely to be a big match for the former Charlton Athletic man, who is only playing because Dutch international Tim Krul is injured.
11 minHaving made a slow start, Anzhi are now seeing an awful lot of the ball. Unsurprisingly, it looks as though one of the major tactics is to get the ball into Willian's feet and let him cause some problems. So far, the Brazilian has been kept quiet.
14 minAnzhi's first real opening of the encounter has just been wasted by Oleg Shatov. Diarra and Willian linked brilliantly to free the striker, but instead of shooting he opted to cross from the left and the danger was cleared. Warning signs for Newcastle nonetheless.
18 minNewcastle really are offering very little as an attacking threat at the moment. To be honest, it is hard to work out who is actually playing up front. It looks as though both Ben Arfa and Sissoko are sharing the duties. Whoever takes on the role will need more support than they are currently getting.
22 minSUBSTITUTION: Great news for Newcastle fans, but not so good for supporters of Anzhi or the neutrals. Willian's game is over as he appears to have picked up an ankle injury. It's a major positive for Newcastle, because everything the Russians did went through Willian, who has been replaced by Lacina Traore.
26 minIt's still Anzhi that are dominating the possession, but to be honest they have done very little with the ball. It's not like you can say that Newcastle have played well defensively because they haven't had a lot to do. This game needs a goal to spark it into life.
30 minVery poor play from the substitute Traore, who would have been in on goal but for a poor run. Eto'o broke free inside the the Newcastle half, but Traore had strayed way offside and the flag was raised as Eto'o threaded through a pass. Needless from the Anzhi attacker.
33 minBOOKING! First yellow of the match and Newcastle's Massadio Haidara can have no complaints. He was beaten all ends up on the right wing by Odil Akhmedov and then decided to pull back the Anzhi midfielder right in front of the referee.
37 minHave to say, the delivery from corners, free kicks and crosses has been poor from both sides so far. Newcastle have got into advanced positions on a couple of occasions, but the danger has been easily erased. It's the same where Anzhi are concerned. Neither manager will be happy with what they have seen from an attacking point of view.
40 minSAVE! Elliot - you lucky, lucky goalkeeper! Eto'o tries his luck from 25 yards, but strikes the ball straight at the Newcastle stopper. He almost makes a howler of it though as the ball springs out of his hands and squirms just over the crossbar for a corner, which comes to nothing.
45 minThere will be a minimum of one minute of stoppage time here in Russia...
5.50pmWell, there is little doubt that Pardew will be the happier of the two gaffers after that 45 minutes. His Newcastle side may not have posed much of a threat, but they have looked solid at the back. If they can be a bit more adventurous after the restart, there is a chance that they could collect a positive result from this one.
5.54pmFrom Anzhi's point of view, they must do better when they have the ball. They've had the lion's share of the possession, but created very little with it. It won't have helped that their playmaker Willian was forced off early with an injury. He is the focal point of their team and they have struggled since his exit.
5.56pmHere is a tweet from Opta that just about sums up that first half:
"39 - The first shot in Anzhi vs. Newcastle Utd came in the 39th minute, the longest wait for a shot in a Europa League game this season. Shy."
6pmTalking of shots, Newcastle didn't actually have one on or off target during those opening 45 minutes. Let's hope Pardew tells his team to be more positive in the second half because as we've seen so often in these tournaments, an away goal can be crucial. Perhaps bringing on Shola Ameobi could help them create more chances.
45 minRight, Anzhi get what is hopefully going to be a better second half started. Even a shot would do!
49 minWell, the second half has started in exactly the same way that the opening 45 minutes panned out. Anzhi are seeing virtually all of the ball, but have shown no signs of breaking through the Newcastle rearguard. It's a real shame that Willian was forced off because he has the ability to create openings - although I'm sure that Newcastle fans do not share that point of view!
53 minGood stuff from Newcastle's James Perch, who gets straight back up after being accidentally clattered in the face by Traore. He could have made a meal of that and rolled around, but he saved his Anzhi counterpart from collecting a yellow card there. If only all footballers had that attitude!
57 minAny danger of either side having a shot?! The Anzhi dominance has continued, but just like in the first half, their crossing has been woeful - and that is being kind. It's been an easy evening's work for the Newcastle defence so far.
60 minSAVE! Hallelujah, we've had an effort at goal. It's actually a very good save from Elliot, who got down to his right to turn a low drive from Eto'o around the post. The resultant corner falls to Shatov on the edge of the area, but he sends a volleyed effort a couple of yards wide of the target. That's much better from the home team.
64 minSAVE! How an earth are Newcastle not in front here? I had to rub my eyes to make sure, but they actually mounted an attack and should be winning. Yohan Cabaye picks out Ben Arfa all alone inside the area, but the Frenchman tried to be too casual and lifts the ball, which is easily saved by Vladimir Gabulov in the home goal. Shocking miss. That was actually Ben Arfa's last involvement as he has now been replaced by Shola Ameobi.
68 minAfter that mad couple of minutes where both sides created chances, the tie has now settled back into a mundane rhythm. Anzhi are doing the majority of the attacking, but they don't look to have too many ideas.
71 minCHANCE! It's by no means a clear cut opportunity, but Anita has just took aim for Newcastle about 30 yards from goal. Credit to the midfielder, because the ball only just flew over the bar.
75 minSUBSTITUTION: And that is the last act from Anita. He has been taken off, with Steven Taylor coming on in his place. You can tell that Taylor is from Newcastle because he is wearing a short sleeve shirt with no sign of gloves!
Sponsored:Bet £25 and get a £25 FREE bet with William Hill, click here to join now. T&Cs apply, new customers only
79 minIt cannot be stressed enough just how poor the deliveries from corners and crosses has been this evening. The latest to offend is Newcastle's Sylvain Marveaux, who sends a corner straight to the Anzhi player standing at the near post. It's a wasted chance for the away side, because they had sent the likes of Taylor up to try and cause problems.
83 minSUBSTITUTION: Another switch for Newcastle as skipper Cabaye is replaced by Cheick Tiote, who takes the armband from his teammate. What are the odds on him getting booked between now and the end of the game? It doesn't normally take him too long to get his name taken down!
87 minSAVE! Top defending from Taylor, who for a moment looked as though he was going to be turned inside out by Eto'o. As it was, the Newcastle defender forced the Cameroon international wide and when he did eventually shoot, the contact was poor and the ball trickled towards Elliot. The Eto'o of Barcelona would have done a lot better with that chance.
89 minSUBSTITUTION: A change for the home side as full-back Eshchenko limps out of the action and is replaced by Logashov. The youngster recently won his first senior cap for Russia under the management of Fabio Capello.
90 minThere will be three minutes of stoppage time for one of these sides to find the goal that would give them the advantage heading in to next week's return leg in Newcastle.
6.53pmThere won't be many neutrals that will remember this match for too long. However, for Newcastle, it could prove to be a crucial result. They will now play host to the Russians in front of their own supporters next week. Despite not having an away goal to show for their efforts, they will arguably be the favourites to progress to the quarter-finals - with Russian teams traditionally not the best travellers in European tournaments.
6.54pmThat's all we have time for from the Russian capital. Thanks for joining us this evening and be sure to stick with Sports Mole as the night progresses for coverage from the other matches in the Europa League. Until next time, goodbye.