Kalle Heikinheimo pääsi ylioppilaaksi Oulun suomalaisesta yhteiskoulusta 1918, minkä jälkeen hän lähti Helsingin yliopistoon opiskelemaan teologiaa.

Hän valmistui papiksi 1923, ja pappisvihkimys tapahtui Oulussa saman vuoden kesäkuussa. Pastoraalitutkinnon hän suoritti 1927. Pappisuransa alussa Heikinheimo toimi ylimääräisenä pappina Rovaniemellä 1923–24, Haapajärvellä 1925, Kuolassa ja Savukoskella 1925 sekä Kärsämäellä 1926–29. Vakinaisissa papinviroissa hän oli Keiteleen kirkkoherrana 1929–35 ja Alajärven kirkkoherrana 1935–41. Viimemainittuna vuotena hän tuli isänsä jalanjäljille Haapajärven kirkkoherraksi. Tässä virassa hän oli kuolemaansa asti. Hänen isänsä Rauno Jalmari (Fredri Hjalmas) Heikinheimo (s. Hailuodossa 26.5.1868, k. Haapajärvellä 23.6.1939) oli ollut Haapajärven kirkkoherrana vuodesta 1910 kuolemaansa vuoteen 1939 saakka. Isä ja poika Heikinheimot toimivat siten kirkkoherroina Haapajärvellä yli puoli vuosisataa ja jättivät vahvan jäljen paikkakunnan elämään.

Oman toimensa ohella Kalle Heikinheimo toimi uskonnonopettajana yhteiskoulussa, oli mukana kansakoulujen johtokunnissa sekä vaalilautakunnan puheenjohtajana. Rovastin arvon hän sai 1950. Heikinheimo oli yhteiskunnallisesti osallistuva, mutta osallistuminen tapahtui pääasiallisesti hänen oman virkansa välityksellä. Hänen ei tarvinnut mennä rintamalle, mutta kotona Haapajärvellä hän oli mies paikallaan. Kaatuneiden omaiset, siirtolaisten evakuointi ja yleensäkin kotirintamaolot tarvitsivat Heikinheimon armolahjoilla varustettua miestä ja pappia. Hän tunsi tarkkaan seurakuntalaisensa, ja häntä pidettiin kansanmiehenä. Hän liikkui mielellään kansan parissa: milloin hän jututti isäntiä markkinoilla, milloin taas tapasi seurakuntalaisiaan liikkuessaan polkupyörällä kaste- ja seuramatkoilla ympäri pitäjää. Kalle Heikinheimon hengellinen koti oli lähinnä uusherätyksessä, mutta sydämen ihmisenä hän suhtautui lämmöllä ja ymmärryksellä myös muihin herätysliikkeisiin, erityisesti herännäisyyteen, jonka vahva tukija oli hänen puolisonsa.

Vanhemmat

rovasti Rauho Jalmari Heikinheimo ja Iines Alfrida Keckman

Puoliso

Eila Hellin Maria Rechardt, syntynyt 5.1.1911 Enontekiö, kuollut 6.2.1995 Vantaa, vanhemmat nimismies Werner Rechardt ja Thyra Lundström