Testaverde connected on a one-yard touchdown pass to James Dearth with 12:50 left and added a two-yarder to Anthony Becht with 6:57 remaining to help the Jets stall, at least temporarily, another late-season slide.
The Jets (8-5) had lost their last five games in December and are just 14-30 in post-November games since 1991.
"Vinny put the team on his shoulders and carried us in the second half," said running back Curtis Martin, who had 78 yards on 24 carries. "We keep hearing about this December thing, but nobody here believes in it. What this win means is we won a game we had to win in order to get out of a slump."
Testaverde found Becht in the back of the end zone for the go-ahead score, capping a seven-play, 69-yard drive that included an 18-yard pass from Testaverde to Laveranues Coles and a 16-yard run by rookie LaMont Jordan.
"My role changes every week and I was glad to have the opportunity to make a big play," Becht said.
Safety Damien Robinson and linebacker James Farrior intercepted passes by Jon Kitna to end Cincinnati's last two drives.
New York won for the first time in three outings and will close the year with games against Indianapolis, Buffalo and Oakland.
"Hopefully the win takes a little sting out of things," Jets coach Herman Edwards said. "The guys we weeded to make big plays made them."
The Bengals (4-9) already are out of playoff contention, and earlier in the week linebacker Takeo Spikes said he would like to take the Jets down with him.
Cincinnati nearly pulled off the upset behind Corey Dillon, who carried 22 times for 85 yards and two scores. Dillon become the sixth player in NFL history to rush for 1,000 yards in each of his first five seasons. But the Bengals suffered their sixth straight defeat.
"Right now we can't win for losing. We're in that kind of a rut," Cincinnati coach Dick LeBeau said. "Yet I was pleased with our overall effort. When you have a lead going in to the fourth quarter, you hope that you're able to hold on."
Testaverde completed 17 of 28 passes for 196 yards.
Kitna replaced an injured Akili Smith in the second quarter and completed 10 of 17 passes for 93 yards with three interceptions. Smith, the third overall pick in the 1999 draft who was making his first start of the season, left the game with a hamstring injury and will miss at least next week's game at Baltimore.
Kitna did not start due to a sprained middle finger on his throwing hand, but refused to use that as an excuse.
"The bottom line is we didn't make the plays we had to make," Kitna said. "No, my finger had absolutely nothing to do with how I played in the fourth quarter."
Smith started strong for the Bengals, guiding Cincinnati on a 12-play, 81-yard drive that took a whopping 12 minutes off the clock. Dillon carried 10 times for 35 yards on the drive, which he capped with a two-yard run over left tackle.
It was the longest scoring drive in terms of plays and yards for the Bengals this season.
The only score for the Jets in the first half was a 24-yard field goal by John Hall with 18 seconds remaining that made it 7-3. Earlier in the quarter, Hall was wide left on a 40-yard attempt that followed a shaky snap from center.
Dillon again shouldered the burden on a third-quarter drive, carrying six times for 41 yards on a march that ended with his three-yard touchdown run to increase Cincinnati's lead to 14-3.
Cincinnati had a chance to pad its lead less than a minute later, but safety Chris Carter dropped a potential interception with a clear path to the end zone.
"That's the story of our season," Carter said. "We had a lot of teams on the ropes and we have not been able to deliver the knockout punch."
New York finally awoke with a 10-play, 68-yard drive highlighted by a 27-yard pass from Testaverde to Kevin Swayne.
The Jets missed two-point conversion tries on each of their touchdowns.
New York has won the last four games in the series since the Bengals' last win in 1990.