Murray was born in West Runton, Norfolk, to Robert Cameron Brunton Murray and Poppy Katherine Murray () and was raised in neighbouring Sheringham. His father, one of 13 children, had worked in the docks in Leith, Scotland, before joining the Royal Air Force. Murray was educated at Sheringham Primary and then at Paston School, an all-boys state grammar school in North Walsham in Norfolk, which he greatly disliked. He told John Crace in 2007 that pupils were obliged each week to don "military uniform and become cadets. Either I skipped school or refused to take part, so I was frequently suspended". His A-levels suffered as a result.