The world's best striker, Robert Lewandowski put in an underwhelming display for Biało-czerwoni, as he and his teammates were left frustrated by a gritty Slovakia throughout the clash.
Story of the match
As expected Poland had the brighter start out of the two nations, but it was Slovakia who had the first significant chance of the encounter when former Norwich City man Ondrej Duda came close to squeezing a strike past Wojciech Szczęsny at his near post.
The Sokoli did take the lead shortly after however when former Manchester City midfielder Róbert Mak embarked on a mazing solo run, before hitting a low-driven strike which cannoned off Szczęsny to give Slovakia the lead and for all their dominance in the early proceedings, Poland found themselves behind.
Their early heroics boosted the confidence of Slovakia even further and Juraj Kucka of Parma came close to doubling their advantage, his long-range strike going narrowly over the bar.
The first half proved to be a frustrating one for Poland and their star man Lewandowski, with the Bayern Munich man failing to get ahold of his only real opening which came in the latter moments of the first half, his strike posing no threat to Martin Dúbravka.
But whatever Paolo Sousa said to his team at the break worked wonders as just 30 seconds after the restart Poland were level, an intricate team move was finished off by Karol Linetty. The perfect start to the second half for the quarter-finalists from the 2016 tournament.
But in spite of a promising spell from Poland after their equaliser, the balance of play changed on a knife-edge when former PSG midfielder Grzegorz Krychowiak was sent off for a second bookable offence in the 62nd minute, a dream scenario for the Slovakians who were suffering from a barrage of pressure up until that point.
The Krychowiak red card would prove to be the turning point and Poland were punished just minutes later when Milan Škriniar scored just his third international goal and his first in a major competition firing past Szczęsny in the Polish goal.
After retaking the lead Slovakia would close out the game well, showing excellent composure and game management to get their campaign off to a winning start and seal an impressive victory in a game where they were perhaps the underdogs.
An excellent victory for Slovakia which gives them a good opportunity to advance out of the group stages for the second consecutive tournament. As for Poland work to do, but Paolo Sousa's side still have time to turn around their fate in their next two encounters.
Takeaways from the game
Costly red card denies Poland glorious opportunity
After a lacklustre first half showing, Poland started the second half with real impetus and after levelling the game just seconds after the restart it seemed almost certain they would go on to win the game.
A costly error in judgement from Grzegorz Krychowiak, who was shown a second yellow card for catching Jakub Hromada, proved to be the turning point in the game and instantly put the two-time World Cup bronze medalists on the back-foot.
After the dismissal of Krychowiak Poland couldn't combat the threat of Slovakia on the counter-attack, for who the red card couldn't have come at a better time. They would go on to take full advantage sealing a mightily impressive victory in a game in which they were second best for the majority of it.
Man of the match
It proved to be a fantastic evening for Inter Milan star Milan Škriniar, who not only scored the match-winner but also thwarted the threat of the world's best striker.
Škriniar really stepped up for his country on Monday, putting in a fine display and once again demonstrating why he's one of the very best centre backs in Europe.
If the 26-year-old can maintain this level of performance for the rest of the tournament he could lead Slovakia, one of the tournament's big underdogs, out of the group stage to equal their heroics of 2016 when they reached the knockout stages.