But his unsurpassed record is rooted in modesty. Working-class Chicago, military service, losing seasons.
"You can't forget the hunger," Krzyzewski said.
Duke defeated Michigan State on Tuesday at Madison Square Garden for Krzyzewski's 903rd victory, one more than his mentor and college coach, Bob Knight. The evening was more commemoration than game, a tribute to the son of a Windy City elevator operator.
"I was in a no-win situation," Spartans coach Tom Izzo joked during his postgame interview. "I was either going to be the guy who threw the ball to Henry Aaron for the record breaker, or the guy who shot Bambi."
Among Krzyzewski's 903 victories are four national championships, 11 Final Fours and 13 ACC tournament titles. The magnitude of those moments aside, it was a long-forgotten road trip from his final season as Army's coach that truly engaged Krzyzewski when he reflected on his career during the ACC's preseason media gathering last month.
It was late December 1979, and the Cadets first traveled to Santa Clara, Calif., for the Cable Car Classic. There, in the consolation game, Army encountered Virginia and its 7-foot-4 freshman center.
"Ralph Sampson set a school record for blocked shots that still stands," said Krzyzewski, who played point guard at Army for Knight.
Virginia's media guide confirms Krzyzewski's recall. Sampson blocked a Cavaliers-record 12 shots in an 84-60 win.
Per Krzyzewski's memory, Sampson's most frequent foil was Bob Brown, and indeed, the hand-scrawled boxscore from 32 years ago shows Brown shooting 5-for-20.
Today Major General Robert Brown is the commanding general at Fort Benning, Ga., a Bronze Star recipient and a former commander in Operation Iraqi Freedom.
From Santa Clara, Brown and his teammates headed to Hawaii for the Rainbow Classic. After a first-round loss to Illinois, they defeated Princeton 53-52 in a consolation game, setting off a wild on-court celebration.
"That was every bit as big as Final Four moments," Krzyzewski said. "When I stop feeling that way about it, I'll know I'm through coaching."
Army finished 9-17 that season, ending a run of three consecutive winning seasons under Krzyzewski but not deterring then-Duke athletic director Tom Butters from considering him for the Blue Devils' vacancy.
Butters consulted many about his search, including then-Virginia coach Terry Holland, who very much remembered Krzyzewski from their game in Santa Clara.
Now East Carolina's athletic director, Holland said he told Butters that "Krzyzewski's going to think he's died and gone to heaven (at Duke), and he's a (darn) good coach, even though his record this season's going to be a hard sell.
"He's your guy. He'll love Duke. He'll think, 'You mean, our guys don't have to drill in the afternoon before they come to practice?' "
Holland was right. Krzyzewski fell for Duke. But the love-at-first-sight was not mutual as his first three teams went 38-47, 13-29 in the ACC.
Butters remained confident in his choice and today, at age 64 and in his 32nd year at Duke, Krzyzewski shows no signs of slowing.
"I still have my passion to prepare and be good," he said at the preseason function. "Now we'll find out if we are good."
When isn't Duke good? The Blue Devils have reached 27 NCAA tournaments in the last 28 years and won their most recent national title in 2010. They're the ACC tournament's three-time defending champions and have finished 11-5 or better in the conference 14 of the last 15 years.
"We don't have Jeter or Rivera for 15 straight years and you have to do it in intense competition at a great school," Krzyzewski said Tuesday after accepting the game ball from NCAA president Mark Emmert.
Like North Carolina's Dean Smith when he became the career wins leader in 1997, Krzyzewski was surrounded by former players Tuesday. Shane Battier, Carlos Boozer, Grant Hill, Mike Dunleavy, Chris Duhon.
"We live with a few other programs recognized as elite programs," Krzyzewski said, "but it hasn't always been that way. I think the reason we've won is because I had those (tough) years. I know what it is to lose. I know what it is to feel bad. I know. …
"If you spend 10 years of your life — this is my 37th year as a (head) coach — 10 of those years, those were hard, hard years. And so I never forget those things. I don't want to go back."
David Teel can be reached at 757-247-4636 or by email at email@example.com. For more from Teel, read his blog at dailypress.com/sports/teeltime and follow him at twitter.com/DavidTeelatDP