Paul Nicolas è considerato uno dei migliori calciatori francesi dell'anteguerra. La sua fama è legata ai successi ottenuti con il Red Star, con cui vinse 4 volte la Coppa di Francia (1921, 1922, 1923, 1928) arrivando ad avere uno dei migliori palmarès della sua epoca, e alle reti segnate con la Nazionale, con la quale prese parte anche a tre Olimpiadi (1920, 1924, 1928). In seguito allenò per lungo tempo la Nazionale francese.