Fils de René Deheuvels, Paul naît en 1948 à Istanbul où son père est professeur au lycée de Galatasaray et où sa mère est fille du consul général de France.

Il intègre l'Ecole normale supérieure - où l'avait précédé son père -, est agrégé de mathématiques en 1969 et docteur d'Etat en 1974.

Il fait toute sa carrière à l'université Paris VI (Jussieu, Pierre-et-Marie-Curie). Il est l'un des meilleurs spécialistes de la statistique théorique et la théorie des probabilités, notamment dans les domaines de la théorie des valeurs extrêmes, des processus empiriques et de quantiles, de l’estimation non paramétrique, des copules, des lois limites et des approximations fortes.

Il a reçu le prix Pierre-Simon de Laplace, de la Société française de statistique en 2007. Des Mélanges lui sont remis en 2015.

Il est élu correspondant de l’Académie des sciences en 1996, puis membre en 2000 (section des Sciences mécaniques et informatiques et inter-section des applications des sciences).