He formed the band Skog together with Øye in the 1990s. They formed Kings of Convenience in 1998 and released their first album Quiet is the New Loud in 2001. Øye had become interested in electronic music and in October 2001 they released the remix album Versus. The single "Toxic Girl" brought Bøe's music to the attention of fans and received critical acclaim for its unpretentious simplicity and lyrical quality. In 2004 Kings of Convenience released Riot on an Empty Street which was followed by a European and North American tour in 2005.
In 2006 he supported Øye's band The Whitest Boy Alive at some dates on their Scandinavian tour with another band Kommode. Kommode features members of Skog, except for Øye.
In a rare guest vocal appearance, Bøe sings on the track "How My Heart Behaves" on Feist's 2007 release, The Reminder.
In October 2009 Kings of Convenience released a third studio album Declaration of Dependence on the Astralwerks label, this was considered one of the best albums of the decade.