Paul Motian örmény származású családban született 1931-ben; vezetéknevét egyszerűen úgy ejtette, mint az angol "motion" szót. Providence-ben nőtt fel, tizenkét éves korától dobolt; a helyi jazz-életbe hamar bekapcsolódott. 1950-ben belépett a haditengerészetbe, majd 1953-ban New Yorkban telepedett le. Az ötvenes évek közepétől a hatvanas évek végéig, mint később egy interjúban mondta, "volt egy hosszú időszak, amikor minden este játszottam." Megfordult Lee Konitz, Stan Getz, Tony Scott és mások zenekaraiban, egy hétig még Thelonious Monkéban is. Bill Evans zongoristával 1955-ben ismerkedett meg, egy évvel később debütáló lemezén is játszott (New Jazz Conceptions). Igazán nagy hatású a később megalakult Bill Evans Trio volt, amelyben a névadó és Motian mellett Scott LaFaro bőgős játszott. Az 1961-ben megjelent Sunday At The Village Vanguard és Waltz For Debby című lemezeiket a jazz történetének legnagyobb klasszikusai között tartják számon. Többek között azért, mert a zongora-bőgő-dob trió újfajta felfogása jelent meg a zenében: nem a szólózenész - kíséret hierarchia jellemezte, hanem az egyenrangú közös játék. "Tudtuk, hogy valami különleges, eredeti, soha korábban nem hallott dolgot csináltunk; hogy újszerű módon fogtuk fel, hogy mit jelent trióban játszani. Nem arról volt szó, hogy van a zongora, a bőgő és a dob, hanem arról, hogy három ember együtt zenél" - mondta Paul Motian később.

Mindkét lemezt 1961. június 25-én vették fel; július 6-án Scott LaFaro autóbalesetben elhunyt. Paul Motian 1964-ig játszott még Bill Evansszel, majd a Paul Bley zongoristával való közös munka volt rá nagy hatással. Erre így emlékezett vissza: "vele nem volt semmilyen korlát, még előre adott formák sem - csak a teljes, már-már a káosszal határos szabadság." Majd egy újabb zongorista, Keith Jarrett mellett játszott nagyjából egy évtizeden keresztül. 1967-ben szerepelt az első olyan lemezen, ami Jarrett neve alatt jelent meg, illetve az ún. amerikai kvartett tagja volt. Emellett zenélt másokkal is (többek között: Don Cherry, Carla Bley, Charlie Haden's Liberation Music Orchestra stb.); ő kísérte Arlo Guthrie folkénekest a Woodstock fesztiválon.