Callejon was founded in 2002. Their first release was a self-titled demo released in 2003. On 7 May 2005, the band released their EP Chronos. Their debut album, Willkommen im Beerdigungscafé, was released on 7 July 2006. Both albums were released through their label "My Favorite Toy Records", which is based in Mainz.
In February 2003 the band went on a three-weeks promotional tour for their album Willkommen im Beerdigungscafé
In September 2007 they signed a contract with Edition TAKK, a publishing company associated with Sony/ATV Music Publishing Germany. With a tour in winter 2007 the EP Fauler Zauber Dunkelherz was promoted. After that drummer Sven Wasel was replaced by Bodo Stricker.
In May 2008 the band signed a contract with Nuclear Blast. Their label debut Zombieactionhauptquartier contained 13 songs. It was produced by Eike Freese in Hamburg and was published on 28 November 2008. The album features a song Porn from Spain with Nico from K.I.Z rapping as guest singer.
In March 2010 the band uploaded their third album Videodrom to their Myspace page. It was released on 3 April 2010 and entered the German Media Control Charts at No. 31. The Album is inspired by David Cronenberg's film Videodrome.
Their album Blitzkreuz, produced by Colin Richardson, was released in June 2012. A video for the first single "Blitzkreuz" has been released on April 12.
With their album Man Spricht Deutsch they released a album consisting only of cover versions in January 2013. Fanart Banner