Paul cresceu em Chingford, subúrbio de Londres, e durante a adolescência cantou em várias bandas de rock enquanto trabalhava como açougueiro e cozinheiro. Ele entrou no Iron Maiden após a saída de Dennis Wilcock, sendo apresentado a Steve Harris pelo baterista Doug Sampson, um velho amigo de Steve que tocou com ele na banda Smiler. Foi nesta época que Paul adotou o sobrenome "Di'Anno" – que depois ele usaria para afirmar ser descendente de italianos.

O primeiro teste com Paul não ocorreu, porque Paul foi preso pela polícia ao ameaçar um homem com uma faca em via pública, mas Paul acabou entrando na banda e gravando o primeiro álbum em 1980, Iron Maiden, que tornou-se um clássico do gênero, misturando punk com riffs de heavy metal e alguns elementos de rock progressivo. Em 1981, Paul gravou o segundo álbum, Killers, e um EP, Maiden Japan.

Tensões começaram a surgir na banda por causa do comportamento de Paul. Alguns shows chegaram a ser cancelados por falta de vontade ou pelo estado em que Paul se encontrava, pelo uso excessivo de bebidas alcoólicas e drogas. Por causa desses problemas, a banda resolveu substituí-lo por outro vocalista que conseguisse cumprir os compromissos das turnês, e acabaram escolhendo o ex-vocalista do Samson, Bruce Dickinson.

Após a saída do Iron Maiden, Paul montou uma banda própria chamada Di'Anno, com Lee Slater e P.J. Ward nas guitarras, Kevin Browne no contra-baixo, Mark Venables nos teclados e Dave Irving na bateria. A banda perdurou por dois anos, gravando apenas um álbum (Di'anno) em 1984.

Em 1985, Di'Anno criou a banda Battlezone, com a qual fez shows por quatro anos e gravou 3 álbuns: Fighting Back, Children of Madness e Warchild.

Após o fim da Battlezone, Paul e Steve Hopgood (também integrante do Battlezone) decidiram formar uma nova banda, que Paul nomeou Killers, em homenagem ao seu segundo album no Iron Maiden.