Mentre escrivia per Saturday Night Live, Shaiman començava la seva llarga associació amb Billy Crystal que, (mitjançant Rob Reiner) va portar a fructíferes col·laboracions amb Harry Connick Jr., com per exemple el seu treball com a arranjador a When Harry Met Sally (1989). Aquesta col·laboració el conduïa al naixement de la seva carrera de música de cinema i, encara que categoritzat com a compositor de comèdia romàntica, Shaiman de fet feia el seu debut important el 1990 amb el thriller Misery.[2]