Geneza i nagranie W latach 80. twórczość Everything but the Girl ewoluowała od i gitarowego popu przez aranżacje orkiestrowe do popu opartego na automacie perkusyjnym. Na początku następnej dekady Watt i Thorn zainteresowali się wykorzystaniem i sampli. Do dalszych eksperymentów zachęcił ich remiks utworu „Take Me” z wcześniejszego albumu (1990). Przygotował go duet producencki Bristol Baseline Productions, a remiks wydano jako . Podczas pracy nad Amplified Heart duet zaprosił do współpracy producenta Johna Coxona. „Missing” budowano od partii gitary i wokalu, uzupełniając je elektronicznym rytmem. Zanim Coxon przygotował właściwy podkład rytmiczny, muzycy posługiwali się roboczo pętlą z „Break 4 Love” grupy ; w aranżacji użyli także starych sampli smyczków zaczerpniętych z muzyki klasycznej.
Przystępując do nagrywania „Missing”, Thorn miała już gotową większość tekstu, ale refren pozostawał niedokończony. Jego drugi wers, zawierający porównanie tęsknoty do pustyń pozbawionych deszczu (And I miss you, like the deserts miss the rain), powstał spontanicznie podczas sesji. W późniejszej rozmowie Thorn nie wskazała, które z nich ostatecznie sformułowało ten wers.