Tyus Jones scored 22 points and the Blue Devils (17-2) went on an 18-2 run down the stretch to put Krzyzewski in four figures on his first try.
Jahlil Okafor had 17 points and 10 rebounds, combining with Jones and Quinn Cook (17 points) to fuel the decisive spurt after Duke trailed by 10 with 8 1/2 minutes remaining.
When the final horn sounded, Blue Devils players engulfed Krzyzewski in front of their bench, and he received a bear hug from assistant Jeff Capel. Players were given T-shirts that read "1,000 and Kounting."
"We were so gritty in the last 10 minutes," Krzyzewski said. "It was tough to get involved with 1,000. I was just trying to survive this game, which is how you get to 1,000."
A public address announcement offered congratulations to Krzyzewski from St. John's, and Duke fans at a packed Garden chanted his name and held aloft "K'' signs.
"I'm in it right now. I wasn't in it until now," he said. "You know, to see the happiness of my players makes it good. We have to keep it in perspective. It makes us 17-2 and we've got to go to Notre Dame on Wednesday, but for this moment, for basketball, for the game and for this program, we'll enjoy this one right now."
Sir'Dominic Pointer had 21 points and 10 rebounds for the Red Storm (13-6), who were looking for a huge win to put on their NCAA tournament resume down the road. They were in position to get it, but got worn down by Duke late and let this one slip away.
Rysheed Jordan scored 18 points, and Phil Greene IV added 13. Leading scorer D'Angelo Harrison was held to 12 points on 5-of-14 shooting, his third straight subpar performance as he plays through a strained calf.
No. 1,000 came about 500 miles from the cramped and cozy confines of Cameron Indoor Stadium, but Coach K was hardly on unfamiliar soil.
After all, Madison Square Garden was where he notched win No. 903 against Michigan State in November 2011, breaking the Division I record previously held by his college coach and mentor, Bob Knight.
Krzyzewski improved to 1,000-308 in a 40-year coaching career that began in 1975 at his alma mater, Army. He is 927-249 in 35 seasons at Duke, guiding the Blue Devils to four NCAA titles and 11 trips to the Final Four.
By midway through an entertaining first half, the 67-year-old Krzyzewski was on his feet in front of the Duke bench as St. John's erased an 11-point deficit.
Wearing a blue suit and white sneakers to support Coaches vs. Cancer, Krzyzewski stalked after the officials at the end of the first half to argue that Harrison's buzzer-beating 3-pointer came after the shot clock expired.
Coach K didn't get the call, and the Red Storm went into the locker room leading 43-39.
This merchandise is brought to you by Scout Product Review team. We aim to highlight products and services you might find interesting, and if you buy them, we may get a small share of the revenue from the sale.