Eilertsen was born in Trondheim and attended the Trondheim Musikkonservatorium, where he participated in the Jazz program and was part of the Jazz band Dingobats along with fellow students Eirik Hegdal (saxophones), Njål Ølnes (tenor saxophone), Thomas Dahl (guitar) and Sverre Gjørvad (drums), primarily playing Hegdals compositions. He has two band releases as leader of the band Turanga, with band members Fredrik Ljungkvist, Ernst Reijseger, and Thomas Strønen. He also performed with the quartet «Parish», with some of the same members as of «Turanga». In 2006, he released the album Constellations (Jazzaway Records), with the Finnish pianist Alexi Tuomarila's trio, along with Olavi Luohivuori.[1][2][3]