Paul a keletnémet Eisenhuettenstadt-ban született, és az akkor még kommunista Kelet Berlinben nőtt fel. Németország újraegyesítése előtt a határt átszelő rádióhullámok jelentették számára az ablakot a kapitalista világra. Mivel lakóhelyén akkor nem létezett igazi klubkultúra, Paul többnyire a rádiót hallgatta, így találkozott olyan előadók zenéivel, mint például The Smiths vagy a New order.

1989-ben, amikor a fal végre ledőlt, hirtelen széleskörű klubélet indult virágzásnak Berlin-szerte, és bár a techno érvényesült igazán, Paul valami más, egyedibb hangzást keresett.

Ezt a keresést nem adta föl soha. Zenei pályafutását két régi, ócska lemezjátszóval kezdte, és kezdetben remix szalagokat alkotott. Egyedi dance zenei stílusával a közönség először 1991-ben találkozhatott, az akkor még új berlini klubban, a Tresorban. Paul szintén akkoriban kezdett önálló zenei szerzemények alkotásába. Első produkciója 1992-ben jelent meg, a "Perfect Day", melyet "Visions of Shiva"-ként Cosmic Baby-vel együtt alkotott.

1993-ban Paul-é volt az év klubslágere, a Humate "Love Stimulation"-re alkotott remixe. A következő évben megjelent első lemeze, a 45 RPM , és a legendás berlini klub, "E-Werk" rendszeres fellépője volt.

A következő években Paul még több elismerést szerzett, olyan híres előadók számainak remixeivel, mint az Inspiral Carpets, Sven Väth, Curve és a New Order. Második lemeze, a Seven Ways , stabilan meghatározta helyét a világ legnagyobb elektronikus zenei előadói között.

A Seven Ways hazai és nemzetközi intejúk áradatát indította el, és Paul hamar a Top 100 közé került, olyannyira hogy végül a dance műfaj rajongói Paul van Dyk-ot 2005-ben a Világ Legjobb DJ-jévé választották a DJ magazin Top 100 listáján. A Grammy díjra jelölt művész, zeneszerző, producer és politikai aktivista az első helyezettnek szóló díjat a londoni Ministry of Sound Clubban megrendezett ünnepségen vehette át.