Yerry Mina's second-half header sent Colombia into a potential last-16 tie with England at the World Cup at the expense of Senegal, who lost out to Japan having received more yellow cards.
Senegal spent the final 20 minutes pushing for an equaliser which would have sent the African side through - Aliou Cisse's side were level with Japan in terms of points and goal difference, but crucially not yellow cards.
Colombia had to win to be sure of their progress but with Poland beating Japan 1-0 in Volgograd, African representation at the World Cup was ended as Senegal failed to secure the point they needed.
The South Americans will face the runners-up from Group G, which will be either England or Belgium, in Moscow on Tuesday, while Japan await the winners in Rostov-on-Don on Monday.
Japan and Senegal finished with identical records in Group H
Senegal thought they had been awarded a 16th-minute penalty after a tackle by Davinson Sanchez on Liverpool's Sadio Mane, but the decision was correctly overturned by Champions League final referee Milorad Mazic, with VAR showing the Tottenham defender clearly touched the ball with what was a risky challenge.
Former England midfielder Danny Murphy, speaking on BBC One, called the tackle "the best of the tournament".
Colombia's chances were dealt a blow just after the half-hour mark as James Rodriguez was forced off due to injury - having missed the first game with a calf problem - four years to the day since his stunning volley against Uruguay in the 2014 World Cup.
But with Barcelona defender Mina's second consecutive goal from Juan Quintero's corner sending Colombia through as group winners, Senegal missed out having received two yellow cards more than Japan.
Senegal reached the quarter-finals of the 2002 World Cup
Senegal were the better side in the first half against a lacklustre Colombia despite having just 43% possession, but Cisse's side failed to find a breakthrough from their two shots on target.
They were forced onto the back foot more after the break as Colombia improved - and should have done better when defending the corner from which Mina scored from.
Senegal improved after conceding, perhaps also knowing Poland had taken the lead against Japan and sensing the onus was back on them to score.
But despite plenty of flair and effort, Senegal were unable to find a way past Arsenal goalkeeper David Ospina, and a pair of yellow cards in the 90th and 91st minute of their 2-2 draw with Japan for Cheikh N'Doye and Youssouf Sabaly retrospectively proved crucial.
Niang was also booked against Colombia, taking their total to six yellow cards in three games compared to Japan's four, as Senegal became the first team to be eliminated via the fair play rule which was only introduced for this tournament.
The Poland-Japan match finished in farcical fashion, with both sides happy to play the ball around at the back for much of the final quarter.
That prompted former England captain Terry Butcher to say on BBC Radio 5 live it "does leave a bitter taste" and that a "magnificent World Cup has been tainted".
BBC football expert Mark Lawrenson, speaking on BBC Two, called the situation a "farce", while also questioning if "there has to be a better way of settling a table in the World Cup".
It means no African team has progressed from the initial group stage of the competition for the first time since 1982.
Colombia failed to register a touch inside the Senegal penalty area in the first 45 minutes at Samara Arena
Colombia failed to register a touch in the Senegal penalty area in the entire first half, with Jose Pekerman's side only correcting that statistic in the 57th minute through substitute Luis Muriel, who had replaced the injured Rodriguez just after the half-hour mark.
Rodriguez had largely been ineffective in his 31 minutes on the pitch for Colombia, although that was the case for all of his team-mates in the opening 45 minutes despite knowing only a win would guarantee their progress.
Colombia, who began the final day in third place in the table after losing to Japan and beating Poland with a significantly-improved performance, could also qualify with a draw if Japan lost due to their better goal difference.
Pekerman's side did only have four touches inside the Senegal penalty area in the second 45 minutes, although one was the key intervention of Mina.
Colombia had 60% of the possession during the match, but worryingly for Pekerman, Mina's header was one of only two shots on target over the 90 minutes, with striker Radamel Falcao largely ineffective.
Senegal coach Aliou Cisse: "It's the law of football. We didn't qualify because we've earned more yellow cards, but I'm proud of my lads, they've worked hard for this tournament and I think we've showed we can have a bright future.
"The rules have been established by Fifa and we have to respect it, even though we would have liked to have been eliminated another way.
"I think the players knew all about it. I'm not going to ask my players to go on the pitch and try to avoid being issued yellow cards. Football is a contact game."
Colombia coach Jose Pekerman: "There is no magic formula to football and one single answer to why one team beats another. I think we worked the set piece very well and that was not a coincidence as we have players who are excellent with their feet and with their head.
"But there were also some very worrying moments, especially in the first half, when Senegal played very well and it was tough for us to maintain our identity. We managed to defend successfully though, and they didn't create many goal scoring opportunities.
"The match was tough because we couldn't get the necessary control in central midfield to enable us to feed the right kind of balls to Radamel Falcao. This was a very even group and you see that with Senegal, who had a very good tournament, going home. There was a lot of tension in the air today and, in that regard, I think my team did very well."
Limey: Senegal only have themselves to blame for that. Waited until they were losing to actually play.
Ashic: Colombia and Japan qualify. Got to feel for Senegal. They were great to watch, but I guess it's only "fair".
Matt: Feeling so sad about that result. No African team in the round of 16.
Goalscorer Yerry Mina also registered a match-leading seven clearances, two interceptions and a 91.4% pass completion rate against Senegal