Paul slowly embarked on a musical career in 1924, singing at an NAACP meeting in Harlem, and throughout the year at parties and small concerts. Initially, he sang popular contemporary songs and European styled songs. However, he felt this stifled his voice and moved to performing songs from his childhood, particularly spirituals.

Believing that the spiritual was the voice of the neglected history of his people, Paul spent his career contending its validity and importance in the face of criticism on every side, most notably from his own race. A wide spectrum of black opinion said that the spiritual was not art, that it pandered to white society, and that whites could only approach listening to it in condescension.

Yet Paul was acutely aware of the necessity to recognize the value of a black culture and its contributions separate from its white surroundings. Further, he was deeply concerned with portraying Blacks as exhibiting all of those emotions which we so often acknowledge as the basis of humanity. This thinking was in response to the two prevailing extreme and distorted portraits of Blacks: one highly caricatured and dehumanized, and the other static, flawless, and perfectly assimilated. To this end, Paul responded to his critics:

“Instead of trying to get away from his folk background, the American Negro should find among his own people the basis of development for his own arts. Some members of my race want to forget how to sing spirituals…There is no good reason for this."

"As to the most important part which the Negro is qualified to play on the American scene, I would define it as “cultural,” with emphasis upon the spiritual aspect of that culture. I would much rather see a world striving for deep cultural and spiritual values which acknowledge no narrow national, racial or religious boundaries.”

Further,
“Negro music portrays the hopes of our people…I am not ashamed of the Spirituals. They represent the soul of my people. White and colored people react alike to the songs. Differences are forgotten and prejudices vanish…Humanity is helped and lifted to higher levels.”