Match ends, Heart of Midlothian 1, Celtic 2.
Celtic manager Ange Postecoglou hailed his side's "resilience and grit" as they survived a second-half scare at Hearts to remain four points off the Scottish Premiership summit.
The visitors led by two after Reo Hatate's long-range drive was followed by a cute Giorgos Giakoumakis finish.
But the hosts improved after the interval as Liam Boyce pulled one back before passing up the chance to equalise when his penalty hit a post.
"I'm very proud," Postecoglou said.
"We had some challenges in terms of personnel but credit to the players, they were fantastic. We played well, created a lot of opportunities and probably should have killed the game off a bit earlier.
"In the end, we had to defend a bit and we did that well."
This win - and Boyce's penalty miss in isolation - could be pinpointed as a massive turning point in the title race come May, should Postecoglou's men manage to catch leaders Rangers, who they host next midweek.
When Hearts condemned Celtic to opening-day defeat in July, Neilson lauded the limited number of 5,500 home fans in attendance, saying they "sounded like 20,000". Six months on, this was a contest worthy of the full house inside Tynecastle.
A raucous crowd watched on under the floodlights as Barrie McKay curled narrowly over for the hosts in a breathless opening.
Celtic debutant Matt O'Riley had a dangerous shot blocked up the other end, but the visitors were creating problems for themselves in defence with slack passes, fuelling a boisterous home crowd.
While the visitors were looking rusty in defence, Jota - on his first start in almost two months - was their sharpest tool as the winger danced past Michael Smith and tested Craig Gordon low at his near post twice in quick succession.
As the half progressed, Celtic began to dictate and broke the deadlock in emphatic style when Hatate's first goal for the club, a searing drive from long range, was too powerful for Gordon.
And just eight minutes later, Postecoglou's men had their second when the impressive O'Riley's low cross from the right found Giakoumakis, who guided in a delightful backheel flick.
Although there were no protests from the home players, replays showed the Greek striker may have been marginally offside.
The home side failed to register a shot on target in the first half, but were much improved in the second as Cammy Devlin slashed a half-volley just wide.
Celtic were still posing a threat, though, with Josip Juranovic's strike needing to be tipped away and Jota having an effort from a tight angle smothered by Gordon.
But the away side's failure to take either of those chances left the door open for the hosts, who capitalised on hesitant defending to pull a goal back.
McKay picked up a bouncing ball and slipped in Boyce, who slid a finish under Joe Hart. Like Giakoumakis in the first half, the Hearts forward appeared to benefit from a marginal offside call.
The Northern Irish striker then had the chance to level the game from the spot after a double handball from Nir Bitton and O'Riley left John Beaton with no choice but to point to the spot.
Boyce sent Hart the wrong way, but saw his penalty strike the inside of the left-hand post before flashing across the face of goal and out of play.
Hearts did not allow that to dishearten them, though, and continued to rally for an equaliser, but Postecoglou's men showed a resilient side to earn a monumental three points.
Man of the match - Matt O'Riley
What did we learn?
Six months on from an opening-day defeat at Tynecastle, this trip was rightly billed as a big hurdle for the visitors to overcome.
The Parkhead club were criticised for being too soft back in late July, when they fell to defeat after a late goal from John Souttar, but this victory highlighted two sides to Postecoglou's Celtic.
The first 45 minutes demonstrated the free-flowing, dominant nature of the team the Australian has built, while the second period proved he has instilled a bit of dig into his players, albeit they benefited from a bit of luck.
The nature of the defeat will hurt for Neilson, as will his team's first-half display, but the Tynecastle boss can take great pride in his players' second-half performance.
The cameo from Beni Baningime will also provide encouragement, who lifted the home side's level on his first appearance since November.
What did they say?
Hearts manager Robbie Neilson: "We started the first 10 minutes really well. Celtic are very good, but we allowed them to be after that period.
"It was a game of two halves. Bringing [Ellis] Simms on gave us a bit of a link up top. Giving him 45 minutes, the players can see what he brings. I think he will be a top player for us."
Both sides return to action on Saturday (15:00 GMT) as Celtic host Dundee United, while Hearts welcome Motherwell.
- 19HalkettBooked at 61minsSubstituted forHallidayat 81'minutes
- 2SmithSubstituted forAtkinsonat 22'minutes
- 14DevlinBooked at 45minsSubstituted forBaningimeat 58'minutes
- 17CochraneSubstituted forMackay-Stevenat 58'minutes
- 30GinnellySubstituted forSimmsat 45'minutes
- 10BoyceBooked at 67mins
- 3TaylorBooked at 45mins
- 33O'RileySubstituted forMcCarthyat 86'minutes
- 6BittonBooked at 53mins
- 41HatateSubstituted forSoroat 90+3'minutes
- 17Neves FilipeBooked at 45minsSubstituted forAbadaat 62'minutes
- John Beaton
- Shots on Target
Second Half ends, Heart of Midlothian 1, Celtic 2.
Substitution, Celtic. Ismaila Soro replaces Reo Hatate.
Giorgos Giakoumakis (Celtic) wins a free kick on the left wing.
Foul by John Souttar (Heart of Midlothian).
Foul by Reo Hatate (Celtic).
Stephen Kingsley (Heart of Midlothian) wins a free kick in the defensive half.
Corner, Heart of Midlothian. Conceded by Greg Taylor.
Attempt missed. Giorgos Giakoumakis (Celtic) left footed shot from more than 35 yards is close, but misses to the right.
Attempt missed. Gary Mackay-Steven (Heart of Midlothian) left footed shot from outside the box is close, but misses to the right following a corner.
Corner, Heart of Midlothian. Conceded by Carl Starfelt.
Substitution, Celtic. James McCarthy replaces Matt O'Riley because of an injury.
Corner, Heart of Midlothian. Conceded by Nir Bitton.
Foul by Carl Starfelt (Celtic).
Ellis Simms (Heart of Midlothian) wins a free kick on the right wing.
Offside, Celtic. Giorgos Giakoumakis tries a through ball, but Liel Abada is caught offside.
Substitution, Heart of Midlothian. Andrew Halliday replaces Craig Halkett because of an injury.
Attempt missed. James Forrest (Celtic) right footed shot from outside the box is high and wide to the right. Assisted by Reo Hatate following a fast break.
Attempt missed. Gary Mackay-Steven (Heart of Midlothian) left footed shot from outside the box misses to the right. Assisted by Peter Haring with a headed pass.
Greg Taylor (Celtic) wins a free kick in the defensive half.