After becoming an All-American playing at UCLA, Naulls was drafted by the St. Louis Hawks in 1956. He spent just 19 games with the Hawks, however, before being traded to the New York Knicks, with whom he would spend the prime of his career. He averaged a double-double (19.3 points per game, 10. 7 rebounds per game) during his seven-year tenure with the team, and he appeared as an NBA All-Star four times. While with the Knicks, Naulls was also the first African-American player to be named captain of a major professional sports team.
During the 1962-63 NBA season, the Knicks traded Naulls to the San Francisco Warriors, who then traded Naulls to the Boston Celtics. Naulls would spend his last three professional seasons with the Celtics, winning three NBA Championship rings in the process. He was a member of the 1964-1965 Celtics team that was named one of the ten best teams in the NBA at the 50th anniversary of the association. Upon retiring in 1966, he had tallied 11,305 career points and 6,508 career rebounds.
On February 24, 2005, Naulls, Campy Russell, and Kenny Walker were honored by the Knicks during their "Hardwood Classics Night."