Karel Paj se je rodil 3. novembra 1918 očetu Francu, železničarju, in materi Dominiki Gerdovič. Imel je mlajšo sestro Albino Paj in polbrata Bruna Gerdoviča. Kot šolar je pomagal staršem tako, da je med poletnimi počitnicami kot pikolo (natakarski vajenec) v kolodvorski restavraciji na Pragerskem potnikom na vlakih, ki so stali na postaji, ponujal pijačo.
Po končani osnovni in srednji šoli se je vpisal na vojaško glasbeno šolo in jo tudi zaključil.
Po nemškem napadu na Jugoslavijo 6. aprila 1941 in hitrem razpadu jugoslovanske vojske je prišel domov na Pragersko. Zaposlil se je v obračunski službi železnice na postaji Pragersko.
Julija 1944 je bil mobiliziran v nemško vojsko.
Že avgusta je kar s straže v avstrijskem Gradcu s sokrajanom, železničarjem Feliksem Vindišem, pobegnil domov, da bi se pridružil partizanom. Z dvema brzostrelkama in pištolo, kar je Paj ukradel nemški vojski, sta uspešno prišla na Pohorje, kjer si je Paj nadel partizansko ime Tarzan. Kot obveščevalec Obveščevalnega centra Pohorje, obveščevalne točke 1C, je bil že po nekaj tednih na Pragerskem, z nalogo zbirati vojaške in druge informacije ter jih po radijski zvezi pošiljati v center. Skrival se je v stanovanju Cvetke Šegula, žene izgnanega nekdanjega šefa postaje Pragersko Leopolda Šegule. V stanovanju Šegulovih je bila namreč pomembna partizanska in obveščevalna javka. Pošto in obveščevalne podatke sta do prihoda Karla Paja do naslednje javke bližje Pohorju prenašala Cvetka Šegula in njen 14-letni sin Rado.
Paja so oskrbeli z daljnogledom in manjšo angleško radijsko oddajno postajo v kovčku. Med enim od zavezniških napadov na Pragersko je eno od nizko letečih letal z rafalom iz mitraljeza zadelo skozi okno tudi stanovanje Šegulovih. Ko je po napadu nemška komisija prišla ocenjevat škodo, je bil v omari skrit Karel Paj z radijsko postajo med koleni. Na srečo jih je Šegulova pregovorila, da omare ni treba odpirati, saj je bila škoda dovolj dobro vidna tudi z zunanje strani. Paj je po prestanem strahu še isto noč zamenjal skrivališče. Za nekaj dni je odšel v Stari Log, nato se je vrnil na Pragersko, tokrat v gostilno Finžgar k Slavinčevim.
Sredi marca 1945 so Karla Paja premestili v godbo Šercerjeve brigade. Z dvema spremljevalcema se je 17. marca odpravil na zborno mesto nad Šoštanjem. Pri Andražu so padli v nemško zasedo. Spremljevalca sta naglo skočila s poti v grmovje in se rešila, Paja pa je stres paraliziral, za hip je okleval in pokosili so ga streli. Ni znano, kje je pokopan.
Pionirski odred OŠ Pragersko se je imenoval po Karlu Paju, ulica, ki pelje mimo šole, se še danes imenuje po njem.