Nasce in una famiglia di umili origini (il padre era disabile, mentre la madre, per tirare avanti, era costretta a fare saltuariamente pulizie a domicilio), costretta a traslocare spesso. Nel 1970 si stabiliscono a Clapton, e poco tempo dopo nasce la sua grande passione per la musica, che si contrappone ad uno scarsissimo interesse per la scuola. Il suo strumento preferito è la chitarra, ascoltava prevalentemente blues e il suo idolo è Jimi Hendrix: «Avevo 15 anni quando sentii "Voodoo Child" alla radio. Da quel momento tutta la mia vita è cambiata».
Paradossalmente, è a scuola che Dave ha la possibilità di formare il suo primo gruppo blues con Adrian Smith, gli Evil Ways. Con la fine della scuola nel 1974 la band si scioglie e Dave rimane nell'inattività fino al 1976, anno in cui entra a far parte degli Iron Maiden di Steve Harris.
La sua militanza risale agli albori della storia della band, quando alla voce c'era ancora Dennis Wilcock. Sebbene amico di Harris, il rapporto tra Wilcock e Murray era piuttosto ostile e la rivalità tra i due portò il chitarrista ad uscire dal gruppo solo dopo sei mesi (il motivo pare fu da rimandare all'atteggiamento dispotico di Wilcock). Nel frattempo Murray entrò a far parte degli Urchin, il cui leader è Adrian Smith. Tuttavia, dopo pochi mesi, Harris allontanò Wilcock dagli Iron Maiden, spinto dal suo atteggiamento arrogante e dittatoriale (era riuscito a far entrare nel gruppo una tastiera per la prima ed ultima volta), e richiamò definitivamente Murray.