W niepodległej Polsce Karol Holeksa został wybrany już w 1918 do Rady Miasta Krakowa. W 1919 Karol Holeksa otwierał w Krakowie zjazd, na którym powołano Polskie Stronnictwo Chrześcijańskiej Demokracji. W 1920 dokonano połączenia tego stronnictwa z Chrześcijańsko Narodowym Stronnictwem Robotników, tworząc Polskie Stronnictwo Chrześcijańskiej Demokracji.
W latach 1922–1927 sprawował mandat posła na sejm I kadencji wybranego z listy chadeckiej w okręgu 43 Wadowice–Biała–Myślenice–Żywiec-Nowy Targ–Spisz–Orawa. Wybrano go wiceprezesem klubu poselskiego. Był członkiem klubu Chrześcijańsko-Narodowego Stronnictwa PracyTadeusz i Witold Rzepeccy, Sejm i Senat 1922-1927, Poznań 1923, s. 471..
Wystąpił w imieniu klubu na pierwszym posiedzeniu po zamachu majowym. Po wyrażeniu hołdu „pamięci tych, którzy polegli w obronie świętości przysięgi i praworządności” powiedział: „Dalecy jesteśmy od tego, aby tę trybunę zamienić na sąd, a Wysoką Izbę powoływać na sędziów tragicznych wypadków majowych. (...) Stwierdzić jednak musimy, że wypadki te wstrząsnęły podstawami prawa i ładu Rzeczypospolitej (...).