Né le à Berlin[1] en Allemagne, d'un père allemand, professeur de langues slaves né en Tchécoslovaquie, et d'une mère polonaise, professeur de russe dans une grande école technique, il est un enfant souvent malade. Ses problèmes de santé récurrents l'obligent à suivre une cure à six ans. Paul a une sœur qui a trois ans de plus que lui.
C'est vers ses 12 ou 13 ans que ses parents le poussent à faire du piano, comme sa sœur, et qu'il prend des cours particuliers. Mais très vite, il y renonce pour la clarinette. Il passe ensuite à la guitare, sans grande conviction : son père en a une et lui apprend une seule chanson, Wer kann die Lieder der Freiheit verbieten. C'est seulement à 16 ans que Paul finit par s'acheter une guitare électrique de la marque Iris. Un peu plus tard, il apprend la batterie en autodidacte, et se sert de celle de Till Lindemann (chanteur actuel de Rammstein) pour s'entraîner.
L'année de ses 14 ans, ses parents divorcent. Paul reste avec sa mère qui se remarie bientôt. Deux ans plus tard, il quitte sa famille car il ne s'entend pas avec son beau-père. Il déménage à Berlin et travaille comme chauffeur à la bibliothèque de Berlin-Treptow, sans avoir le permis.
C'est en 1982 que Paul rencontre Alexander Kriening, l'un des membres fondateurs du groupe punk Feeling B. À l'époque, Kriening joue de la batterie dans un groupe nommé Feeling 14 dont Aljoscha Rompe est le chanteur. Lorsque ce groupe se sépare, Paul accepte de rejoindre Kriening et Aljoscha, non sans quelques réticences. Ils adoptent le nom de Feeling Berlin, qu'ils changent vite en Feeling B pour se dissocier d'un autre groupe du même nom. C'est aussi grâce à Feeling B que Paul rencontre Christoph Schneider, en 1990, lorsque ce dernier remplace le batteur. Il est le cinquième musicien à rejoindre Rammstein, pour qui il n'est, à la base, qu'ingénieur du son. C'est Till qui insiste pour qu'il intègre la bande en tant que second guitariste, malgré les réticences de Richard et de Schneider, ce dernier ayant peu apprécié la manière dont un concert de Feeling B à Ilmenau s'est passé
[2].
Paul se marie en 1984. Le mariage se déroule sans aucune cérémonie, et est plus une manière symbolique pour lui de s'émanciper. Comme le permet la tradition allemande, Paul adopte le nom de son épouse, auquel il trouve une bien meilleure consonance que le sien. Pour lui, Paul Landers est aussi un nom tout à fait digne d'une rockstar et c'est pour cette raison qu'il le conserve même après leur rupture en 1986. Ils cohabitent jusqu'en 1987-88 puis divorcent.
Son fils, né au début des années 1990, Emil, est issu d'une brève relation avec une autre femme. Paul ne se remarie pas. Depuis 1997, il est en couple, et a une fille prénommée Lilli.
Paul est un homme d'un caractère jovial bien qu'on ait appris en 2007 qu'il pouvait être aussi sujet à de courtes dépressions.
Il est très bavard en interview mais, revers de la médaille, a donné trop d'informations prématurées, se révélant fausses. De nombreux amateurs du groupe prennent donc désormais ses déclarations avec des pincettes.