Nat Holman joined the City College staff as a tutor in hygiene with the added responsibility of varsity soccer coach and freshmen basketball coach in 1917 after graduating from the Savage School. He was 21 years old when he coached his first soccer game. As the school's first soccer coach with wins over Yale, Princeton and the Crescent Athletic Club, the team was recognized as the best in the East. The following year he enlisted in the Navy with America's entry into War World I where he served six months as the athletic instructor at the Federal-Rendezvous Naval Training base in Brooklyn. He returned to City College a year later and took over coaching the varsity basketball team at the age of 23 (he also coached the City College baseball team 1920-1925 in competitive play with wins over the strongest teams in the East, including Lafayette). As the youngest basketball head coach in the country many of the players were his age. Nevertheless, he made the adjustment and began a remarkable run of 30 winning seasons in 37 years (his only losing seasons were from 1942-1944, due to America's entry into World War II, and 1952, 1955, 1956, and 1959).
In his first year as basketball coach at City College he used strategies and techniques that he had learned playing with the Celtics that he taught to his players. Holman had an unusual arrangement with City College when he was hired as the school's basketball coach; they allowed him to continue playing professional basketball. At times there was a scheduling conflict and he would have to leave a City College game a little early or have Morris, his younger brother, take over the coaching duties when he was on the road and could not get back in time. But when Holman was coaching he was the master. Some referred to him as the "Old Master" because of his demand for perfection. Holman demanded his players give 100 per cent effort every time they stepped onto the basketball court to practice or play in a game. He could not tolerate or accept anything less than perfection. At basketball practice he would coach his players through a heavy workout on the court pushing and pulling them as if they were life-sized chess pieces. He was as good at coaching as he was at playing. His skill came not only from his status as a professional athlete but also a personality who displayed and, therefore, inspired confidence. When he was hired as head basketball coach in 1919 he immediately adopted a winning attitude. His teams mirrored the confidence Holman had as a player. His teams were always prepared and skilled in basketball fundamentals.
Holman was a fundamentalist of the game. He had phenomenal success working with players of little previous experience. Year in and year out, Holman would take average players and develop them into a cohesive team that played as one. Most of the players who came to City College were not high school basketball stars. Those players usually went to other schools where they were on scholarships (City College did not offer its student athletes scholarships because tuition was free, supported by city tax revenues). As a result Holman had to develop second-tier players into a team capable of holding its own against the top teams in the country. This indeed is a measure of Holman's success when his win-loss record of 421-188 is considered. Over time Holman wiped out City College's reputation as a subway school by making the nation associate City College with basketball. Winning teams brought the alumni and the student body together at Madison Square Garden for exciting basketball, where chants of "Allagaroo-garoo-gara" resounded.