A sziléziai Gräfenbergben (mai nevén Lázně Jeseník; németül Freiwaldau – a város jelenleg Csehországhoz tartozik) született 1849-ben. Édesapja osztrák származású[2] belasi Khuen Antal (1817–1886) gróf, édesanyja monostori és komlósi Izdenczy Angelika (1823–1894) bárónő volt. Az apai nagyszülei idősebb belasi Khuen Antal, földbirtokos és gróf Viczay Karolina voltak. Az anyai nagyszülei báró monostori és komlósi Izdenczy József (1790–1868), országgyűlési követ, földbirtokos és gyulavarsándi Névery Mária voltak. Khuen-Héderváry Károly szülei házasságából tíz gyermek született, akik közül hárman kiskorukban meghaltak: Egon (1848–1850), Irma (1853–1859) és Paula (1866–1867). Hét felnőttkort megért gyermekük:
Károly
Alice (1850–1879), Zichy Zsigmond, császári és királyi kamarás és főhadnagy neje, akivel 1877. január 8-án kelt egybe.
Antal (1852–1890), császári és királyi kamarás, a horvát országgyűlés tagja, neves építész
Angelika (1855–1918), aki 1887-ben Lodron-Laterano Albert felesége lett.
Henrik (1860–1928), császári és királyi kamarás és főhadnagy a lovastestőrségnél
Szabina (1863–1942), aki 1883-ban Woracziczky János felesége lett.
Az utolsó Viczay gróf, Viczay Héder végakaratának megfelelően és legfelsőbb határozattal (kelt Bécsben, 1874. december 5-én) Károly engedélyt kapott a névmagyarosítás jegyében a Khuen-Héderváry kettős név viselésére, előnevét belásiról hédervárira cserélte, címerét pedig a két család címeréből állította össze. Khuen Károly anyai nagyanyja Viczay Karolina, aki egyben Viczay Héder nagynénje is volt. Emellett más családi kapcsolat is volt a két család között, Viczay Héder testvére, Viczay Károly (1802–1867) Khuen-Héderváry Károly nagynénjét, Khuen Máriát (1811–1848) vette feleségül.
Az 1874. december 5-énBécsben kelt legfelsőbb határozat alapján, az utolsó gróf loósi és hédervári Viczay (Viczay Héder) után családneve mellé felvette a Héderváry nevet, a belásinemesi előnevet pedig hédervárira cserélte, valamint a Khuen család címerét egyesítette a Viczay családéval.
Az uralkodó 1882. január 1-jén kinevezte Győr vármegyefőispánjává, beiktatása február 6-án történt, ahol árvizek idején elsőrendű irányító tehetségnek bizonyult. Hogy rendezze az ottani anarchikus viszályokat, Horvát-, Szlavón- és Dalmátországbánjává történő kinevezést kapott 1883. december 1-jén, és ezt húsz éven keresztül megtartotta. Ezzel egy időben elnyerte a valóságos belső titkos tanácsosi és a császári és királyi kamarási címet. Csakhamar bekerült a horvát országgyűlésbe, onnan pedig a magyarba. A kezdeti nehézségekkel szerencsésen és erélyesen megküzdött, lecsillapította a felizgatott kedélyeket, rendezte a zilált horvát pártviszonyokat, megszilárdította a magyar állameszmét, megteremtette a Horvát Nemzeti Pártot, nagy reformokat hajtott végre különösen a közigazgatás és a tanügy terén. A horvátok számára azonban hátrányos intézkedésekkel érte el ezeket: Horvátországban erőszakos magyarosítást hajtott végre, a magyar nemzeti szimbólumok elterjesztésével és a magyar nyelv használatának kiterjesztésével. Ellenzékét a horvát–szerb ellentétek szításával gyengítette. A horvátországi választójogi törvényt módosította: szűkítette a választásra jogosultak körét, ezzel biztosítva uralmát.[5] A magyarosító politika ellen több tüntetés volt, ezek közül a legjelentősebb: a császár 1895-ös zágrábi látogatása során egy csoport horvát diák felgyújtotta a magyar zászlót, nacionalista jelszavakat skandálva, így tiltakozva a magyarosítás ellen.
1894. május végén a főrendiházban fölszólalt az egyházpolitikai törvény mellett. Az első Wekerle-kormánymájus 31-ei lemondása után a király őt nevezte ki miniszterelnöknek, de mivel a Szabadelvű Párt határozottan Wekerle Sándor mellett foglalt állást, ezért kabinetalakításáról kénytelen volt lemondani, és Ferenc Józsefjúnius 9-én ismét a lemondott kormányt léptette hivatalba. Hasonló szituáció történt, amikor Wekerle és kormánya – most már véglegesen – lemondott: ismét őt szignálták miniszterelnöknek, de végül Bánffy Dezső alakíthatott kormányt.
Mikor a függetlenségi obstrukcióSzéll Kálmán kormányát megbuktatta, az uralkodó 1903. június 27-én végre őt tette az ország élére, valamint megbízta az újonctöbblet követelésének elejtésével, hogy teremtse meg a békét, és vezesse ki az országot a rossz költségvetési állapotból. A célul tűzött feladatokat azonban nem sikerült teljesítenie, és alig öt hónappal később, november 3-án távozni kényszerült a miniszterelnöki székből.
Ezután, még egyszer nyílott lehetősége kormányt alakítani, 1910. január 17-én, de már a Nemzeti Munkapárt színeiben, aminek egyik alapítója volt. A parlamentben gyakran erőszakos eszközökkel harcolt az ellenzék ellen, aminek következtében végül 1912. április 22-én lemondani kényszerült.
Házassága és leszármazottjai
1880. szeptember 6-án Gyömrőn feleségül vette a magyar főnemesi széki Teleki Margit grófnőt (Gyömrő, 1860. december 2. – Budapest, 1922. január 26.), csillagkeresztes palotahölgyet, akinek a szülei széki Teleki Sándor gróf (1829–1875), aranysarkantyús vitéz, a Szent István rend és a Johannita rend lovagja, nagybirtokos,[6] és gróf széki Teleki Jozefina (1838–1915), az Országos Nőképző Egyesület örökös díszelnöke voltak.[7] Khuen-Héderváry Károly gróf és széki Teleki Margit grófnő frigyéből született:
ifjabb Khuen-Héderváry Károly (Hédervár, 1888. december 16. – Budapest, 1960. június 1.), a felső dunántúli mezőgazdasági kamarák és a Szigetközi Árvízmentesítő Társulat elnöke, a Felsőház tagja, nagybirtokos. 1.f.: Nemes Margit (Temesvár, 1905. február 6. – ?). 2.f.: báró Lidelof Sarolta.