Paolo Troubetzkoy nasce a Intra, sul Lago Maggiore, nel 1866, secondogenito – il fratello Piero diventerà pittore ritrattista – del principe russo Pietro e della cantante americana Ada Winans. L’anno seguente la famiglia si trasferisce nella vicina località di Ghiffa, in una villa in cui vengono frequentemente ospitati personaggi quali i pittori Cremona e Ranzoni, lo scultore Grandi, i musicisti Catalani e Junck, il poeta e compositore Arrigo Boito. Ed è proprio dal particolare impressionismo della pittura scapigliata lombarda, quella di Ranzoni e Cremona, che inizia la ricerca scultorea del giovane Paolo.
Egli nel 1884 si trasferisce a Milano, ma il suo apprendistato – prima con Donato Barcaglia, poi con Ernesto Bazzaro – dura pochi mesi perchè egli mal sopporta lo studio sistematico, preferendo lavorare dal vero, studiando gli animali. A livello espositivo esordisce a Brera nel 1886 con Un cavallo, ma negli anni seguenti comincia ad inviare alle mostra anche dei ritratti.
Nei primi anni novanta partecipa a numerosi concorsi per monumenti alle glorie nazionali – tra cui Garibaldi, Fanti, Dante, Amedeo IV di Savoia – da erigersi in varie città italiane, mentre alcune sue opere vengono acquistate dalla Galleria Nazionale d’Arte Moderna di Roma e dal Golden Gate Museum di San Francisco.