Wesley Iwundu added 10 points, including a free throw after Henderson's missed 3-pointer, as the Wildcats (5-3) beat the Rebels (6-1) for the first time in five tries.
Henderson, the flamboyant guard who dazzled in last year's NCAA tournament, finished with 13 points but was just 4 of 18 from the field and 2 of 13 from beyond the arc.
Jarvis Summers led the Rebels with 18 points.
Neither team led by more than five points the entire way, and it remained tense in the closing seconds.
Henderson's fade-away 3-pointer with 28.8 seconds left got the Rebels within 59-58, but Will Spradling made one of two free throws to give Kansas State a cushion.
Ole Miss raced the ball up court, and Derrick Millinghaus got the ball in the hands of Henderson, who let go with a tightly guarded 3-pointer from the wing that missed everything.
By the time Iwundu was fouled after the rebound, the Wildcats were already celebrating.
Their victory in the Big 12-SEC Challenge was a good sign of how far the young team has come in a short time. Kansas State lost on its home floor to Northern Colorado in its season opener.
The Wildcats led most of the first half, despite committing nine turnovers, thanks to an ability to break the Rebels' full-court pressure and their dominance of the boards.
Meanwhile, Ole Miss struggled with foul trouble. Post players Anthony Perez, Aaron Jones and Demarco Cox each picked up a pair of fouls shortly after the midway point of the half, forcing coach Andy Kennedy to use some unique substitution patterns just to get to the break.
Henderson's only basket of the half came on a layup with 7:37 left to get Ole Miss within 19-18, but the Wildcats answered with a bucket and two free throws at the other end. When the Rebels pulled even at 25-all later in the half, Kansas State scored the next four points again.
Summers' basket just before the buzzer got the Rebels within 31-29 at the break.
The game remained tight throughout the second half, neither team able to create much separation. For the Wildcats, it was lousy foul shooting that prevented them from pulling away, and for Ole Miss it was miserable shooting from the perimeter that kept it from establishing a lead.
Henderson, who missed his first seven 3-point attempts, finally connected from deep with 5:37 left to knot the game 49-all. Sebastian Saiz's putback and Cox's basket in the paint gave the Rebels a four-point lead, their biggest to that point in the game.
The Wildcats slowly regained the lead from the foul line, despite making one of two on just about every trip, and Foster's 3-pointer with 1:22 remaining gave them a 57-3 lead.
Jones answered with a putback at the other end for Ole Miss, and Shane Southwell was there to pick up a loose ball and scoop in a basket for Kansas State to restore a 59-55 lead with 36 seconds left. Henderson let loose a 3-pointer that splashed through the net with 28.8 seconds remaining.