Georgia, in their first-ever major tournament, needed to overcome one of the tournament favourites in order to secure a dream position in the knockout round of the European Championship.
Kvaratskhelia sent his side ahead in the second minute of the contest, before Mikautadze registered from the penalty spot in the 57th minute to give Portugal a mountain to climb.
Portugal had already won the group ahead of the contest, and Roberto Martinez's side will take on Slovenia in the next round, while Georgia will tackle Spain, having finished in third position in Group F on four points, enough to progress to the next stage.
Kvaratskhelia gave Georgia the perfect start
Kvaratskhelia said ahead of the contest that he had "always dreamed about playing against Cristiano Ronaldo", branding the legendary forward his "idol".
However, it was the Napoli attacker that stole the headlines here; the roof came off inside the stadium in the second minute of the contest, with Kvaratskhelia breaking into the Portugal box before expertly firing the ball past goalkeeper Diogo Costa and into the back of the net.
Antonio Silva will not want to see the goal again, with the Benfica centre-back giving the ball straight to Mikautadze, who then found the Napoli attacker, and it was 1-0 to Georgia soon after.
Georgia held firm after taking an early lead
Ronaldo tested the power of the Georgia goalkeeper's hands in the 17th minute with a rasping free kick from distance; Portugal were threatening, but their frustration was shown in the 28th minute when Ronaldo picked up a yellow card for arguing with the referee over a potential penalty decision.
Ronaldo, who cut an unhappy figure before being replaced in the second half, was again involved in the 35th minute, but the forward's strike from close range was deflected behind for a corner, with Georgia working incredibly hard to keep their lead heading into the half-time interval.
The Al-Nassr forward had another one deflected just over early in the second period, before Kvaratskhelia failed to make the most of a huge opportunity, with the Napoli attacker unable to beat Portugal goalkeeper Costa from inside the box, but the second goal was coming for Georgia.
Penalty incident changed the match
Georgia goalkeeper Giorgi Mamardashvili produced one of the standout saves of the tournament to deny Diogo Dalot, but the play was then halted to have a look at a previous incident, with Silva challenging Otar Kiteishvili inside the Portugal box, and a penalty was awarded following a VAR check.
Mikautadze stepped up to fire into the bottom corner of the net, giving Georgia clear sight of the round of 16, and there was no response from Portugal, although the brilliant Mamardashvili needed to be at full stretch on a couple of occasions in the latter stages.
The result will have given Portugal head coach Martinez much to ponder ahead of the next round, although key players will return to boost the team against Slovenia.
The night belonged to Georgia, though, with the team putting in a heroic performance to secure the most unlikeliest of spots in the knockout round of Euro 2024.
Man of the Match
To a man, Georgia were excellent on Wednesday night, but Kvaratskhelia proved to be the star of the show.
It could have been a completely different match had the forward not scored in the early stages, but he showed class and composure to slide the ball into the bottom corner.
It was a real team performance from Willy Sagnol's side, with Mikautadze and Mamardashvili also standouts, but the result is unlikely to have been possible without the presence of the outstanding player on the field in this contest.
What next for Georgia and Portugal?
Both of these teams have advanced to the next round of the European Championship.
Portugal will face Slovenia for a spot in the quarter-finals of the competition on Monday night, while Georgia's reward for their historic victory will be a clash against the mighty Spain in the round of 16 on Sunday evening.