Allerede medens Paulsen var elev i Odense Katedralskole, modtog han nogen tegneundervisning af sin mor; efter sin konfirmation blev han sat i malerlære, blev elev af sin fødebys tekniske skole og malede på egen hånd studier efter naturen samt mindre billeder, af hvilke sidste han fik et, brystbillede af en lille pige, antaget til udstillingen på Charlottenborg i foråret 1879, samme år, som han blev elev af Kunstakademiet. Dette gennemgik han i løbet af 3 år; inden han forlod det, var han allerede kendt som en ualmindelig lovende ung maler. I 1881 havde således et af hans første landskabsbilleder vakt opmærksomhed, året efter kom bl.a. En gul Rose i et Glas, der med rette betegnedes som et af udstillingens yndefuldeste og ejendommeligste blomstermalerier, og i 1882 Cai, et genreagtigt drengeportræt, udmærket ved kærlig opfattelse og ualmindelig form dygtighed; endnu større anerkendelse end disse arbejder vandt dog i 1883 det legemsstore portræt, Paulsen havde malet efter sin gamle far. I de følgende år udfoldede Paulsen, der i 1888 og 1895 var på længere udenlandsrejser med understøttelse fra Akademiet, en meget omfattende virksomhed og vandt snart anerkendelse som en af de allerbetydeligste danske mestre. Den Neuhausenske Præmie havde han fået for farens portræt; i 1887 tilkendtes han årsmedaljen for Adam og Eva, der desuden erhvervedes til Nationalgalleriet; i 1893 fik han den thorvaldsenske udstillingsmedalje, der medfører sæde i Akademiets plenarforsamling, for et dameportræt. Også på de store internationale kunstudstillinger har han flere gange modtaget hædersbevisninger.
Paulsen har malet historiske genrekompositioner, iblandt hvilke navnlig det ovennævnte Adam og Eva og det i 1898 udstillede Den hellige Cæcilia (Nationalgalleriet) udmærke sig ved inderlig poetisk stemning, storladen stil og glimrende farve; her som i adskillige af sine egentlige genrebilleder viser han sig som en mester i behandlingen af det nøgne legeme, særlig hvor dette stilles op mod en fin og duftig landskabelig baggrund. Som portrætmaler: Faren, Provst Warburg (til Holmens Kirke), Lorenz Frølich (for Udstillingskomiteen), Laurits Tuxen m.fl. – står han i første række, først og fremmest i sin egenskab af klar og åndfuldt forstående karakterskildrer, dernæst ved sin evne til at stille og bevæge figurerne på en i samme grad tiltalende, naturlig og personlig måde; her som i kompositionerne viser han sig tillige som en fremragende formkunstner, en fin og sanddru kolorist. Som landskabsmaler er han blandt alle nyere fortolkere af fædrelandets natur den mest udprægede lyriker. Stærkest giver hans poetiske sjæl sig udtryk, hvor motivet er det simplest mulige, stort plan med få, lidet markerede linjer, god plads til luften. Over for sådanne emner opnår han en betydelig virkning af stemningsfuld harmoni, en rigdom af fint samstemte toner.