Han ble født i Paamiut (dansk: Frederikshåb) på Grønland, og vokste opp i Aasiaat (Egedesminde) som sønn av kateket og organist Peter Olsen og Sofie Andersen. Knud og lillebroren Jørgen ble adoptert av pastor Svend Hertling, og flyttet til Danmark i 1945.
Etter endt universitetsutdannelse ved Københavns Universitet i 1956 fikk han jobb som sekretær i Ministeriet for Grønland. Han ble som en del av denne stillingen sendt til Grønland for å jobbe for Landshøvdingen, og ble der i tre år, fra 1961 til 1964. Han var den eneste tospråklige i Landshøvdingens administrasjon i disse årene. Etter dette ble han bedt om å stille til valg til Folketinget. Han var folketingsmann for Grønlands nordkrets 1964–1973.
Han har vært Grønlandsminister i to danske regjeringer, og var den første grønlenderen som holdt denne stillingen;
I 1969, før han ble minister, stiftet han et politisk parti, Sukaq. Dette var det første politiske partiet på Grønland. Partiet hadde som mål å kjempe for økt grønlandsk selvstendighet, og eget hjemmestyre. Riktignok kjempet han primært for selvstendighet innenfor Det danske Riksfellesskap, slik som Færøyene hadde, men på grunn av sitt arbeid for økt selvstendighet fikk han tilnavnet «hjemmestyrets fader». Men, da han ble minister var dette fortsatt det eneste partiet, og siden han fant det vanskelig å samarbeide med kun ett parti valgte han å oppløse partiet. Da det sosialdemokratiske partiet Siumut ble etablert meldte han seg inn i dette partiet.
