Пісня була записана в 2001-2002, коли група працювала над своїми демо-версіями. Першочергово пісня входила на Б-сторону CD з дебютним синглом «Bring Me to Life». У 2004 пісня «Missing» увійшла до концертного альбому «Anywhere but Home» і стала синглом в США. В тому ж році пісня стала радіо-синглом в Європі та Південній Америці. Офіційна версія і версія радіо-синглу дещо відрізняється: тривалість офіційної версії — 4:16, а радіо-синглу — 3:03.
Створення пісні відбулося під впливом від захоплень гуртом «Portishead». Приспів дуже подібний на пісню «Portishead» — «Wandering Star», а гра барабанів на їх пісню «Numb».