Erlend Øye e Eirik Glambæk Bøe sono nati entrambi a Bergen, in Norvegia, nel 1975. Si sono conosciuti a scuola ed hanno suonato nella stessa band, gli Skog, prima di sciogliersi e dare vita ai Kings of Convenience nel 1999.  In seguito a delle apparizioni in alcuni festival europei, il duo trova un contratto con la casa discografica americana Kindercore. Dopo un breve periodo di lavoro a Londra con l’allora produttore artistico dei Coldplay Ken Nelson, nel 2000 i KOC pubblicano il loro primo album, “Kings of Convenience”,  diretto al solo mercato statunitense e canadese. Il loro debutto su scala mondiale avviene invece l’anno successivo, con “Quiet Is the New Loud”: l’album riprende molte delle tracce già presenti in “Kings of Convenience”, con l’aggiunta di alcune nuove canzoni. Con quest’album il gruppo raggiunge un notevole successo, tanto da dare vita ad una vera e propria nuova scena musicale underground: new acoustic movement, che prende ispirazione dallo stile di Simon & Garfunkel puntando su melodie intricate, sofisticate e molto delicate.

Tale è il successo del loro album che nel 2001 viene pubblicato “Versus”, un album di remix delle tracce di “Quiet Is the New Loud”.

Il secondo album di inediti viene pubblicato nel 2004: “Riot on an Empty Street” suscita un enorme ed inaspettato successo di pubblico, mostrando anche una forte evoluzione nello stile del duo. Mentre le sonorità complesse e delicate rimangono, viene utilizzata una maggiore varietà di strumenti, con un forte apporto di pianoforti e di archi accanto alle irrinunciabili chitarre. Il primo singolo ”Misread” diviene una delle canzoni più popolari dell’estate 2004 -Anche il secondo singolo, ”I’d Rather Dance with You”, accompagnato da un videoclip  molto ironico che gioca sull’aspetto “da secchione” di Øye, viene trasmesso frequentemente dalle televisioni musicali arrivando a vincere gli Mtv Music Awards del 2004 nella categoria miglior video. L’album del 2004 vede anche la collaborazione della cantautrice canadese Leslie Feist in due canzoni: (Know-how e The Build-up).

Nel 2005 il gruppo, stordito dal planetario successo, decide di prendersi una pausa. Durante questo periodo di inattività come Kings of Convenience entrambi i compositori si dedicano a progetti paralleli: Erlend dopo essersi trasferito a Berlino nel 2004 fonda The Whitest Boy Alive, mentre Eirik con gli ex componenti degli Skog dà vita ai Kommode, intraprende gli studi di architettura e diventa padre. Nel giugno del 2008 infine i due si recano all’Esagono Studio di Rubiera, in provincia di Reggio Emilia, città del loro produttore artistico Davide Bertolini, per completare le registrazioni del terzo e ultimo album. Il 25 settembre 2009, cinque anni dopo il precedente, esce quindi: “Declaration of Dependence”.

Il 22 febbraio 2010 esce un loro EP intitolato “Kings of Convenience’s Live Acoustic Sessions – Milan 2009” registrato l’anno prima alla Fnac di Milano.

Sul fronte live i Kings of Convenience hanno continuato a fare tournée in modi sempre nuovi e gratificanti. Nel 2012 hanno suonato spettacoli A-Sides / B-sides: due set totalmente diversi in serate consecutive nella stessa città. Nel 2015, hanno portato in tour “Quiet Is the New Loud” nella sua interezza, insieme a un'intervista sul palco.

Otto anni fa Erlend si trasferisce a Siracusa, in Sicilia, dove nel 2018 insieme a tre musicisti siracusani dà vita al progetto La comitiva con  cui  si esibisce in diverse parti del globo; Eirik invece decide di rimanere a Bergen, dove tuttora vive.