Alig 23 éves anyja két héttel születése után meghalt, apja pedig, aki tekintélyes építőmester, kőfaragó volt, anyai nagyszüleihez adta Nyergesújfalura. Kernstok itt töltötte gyermekkorát, de elemi és középiskoláit már a fővárosban végezte, tanára volt az irodalomtörténész és esztéta Péterfy Jenő is, akiről egyik legkorábbi ismert rajzát készítette.
Alapfokú művészeti ismeretekre nagybátyja, Kernstok József festőművész, a budapesti Iparrajziskola rajztanára oktatta. 1888-ban beiratkozott az Iparművészeti Iskolába, ám onnan 1891-ben eltanácsolták. Ezután Hollósy Simon müncheni festőiskolájában folytatta tanulmányait, 1893-tól a párizsi Julian Akadémiára járt.
Hazatérve 1896-tól három évig Benczúr Gyula mesteriskoláját látogatta, bár annak akadémikus szelleme távol állt tőle.
1897-től újra Párizsban alkotott, 1900-ban Itáliában utazgatott, és Masolino, Masaccio, id. Pieter Bruegel, valamint Rubens művészetét tanulmányozta. A Műcsarnokban kiállított arcképeivel 1898-ban Ráth György-díjat, majd 1900-ban a Műbarátok Köre ösztöndíját nyerte el.
Eleinte Courbet, Millet és Meunier hatása alatt realista és naturalista képeket festett. Nevezetes ifjúkori munkáját, az Agitátor a gyár kantinjában című négy négyzetméteres képét 1896 végén, 1897 elején festette. Ekkor még „Kernstock” formában jegyezte képeit, vezetékneve írásmódját 1900-tól módosította. E korszakának jelentős képe még a Hajóvontatók (1897) és a Munkából című (1901). 1898-ban unokatestvérétől és későbbi feleségétől, Ujváry Ilonától megszületett fia, ifj. Kernstok Károly, aki szintén festő lett.

Kernstok művészetére a századfordulótól egyre jobban hatott az impresszionizmus, olyan plein air képeket alkotott, mint a Diószedők (1900), a Lányok a tornácon (1902), vagy egyik leghíresebb műve, a Szilvaszedők (1901).
1902-ben megtervezte Léderer Artúr fővárosi házának homlokzati mozaikképeit, amelyeket Róth Miksa készített el (Bajza utca 42., ma Oroszország kereskedelmi képviselete). Ezután egyszerűbben, stilizáltan fejezte ki gondolatait, alakjait félhomályba rejtette (Krisztus és az emmauszi ifjak, 1903). Képein a színek játéka később posztimpresszionista hatásokkal együtt tért vissza (Kertben, 1906).