Njuno glasbeno sodelovanje se je začelo leta 1951, Miller pa je s Sinatro posnel njegove največje uspešnice, kot so My Way, Strangers in the Night in Young at Heart. Tudi ko se je pevec povezal s Countom Basijem, je Miller zanj še vedno odigral balade. Izza klavirja ga ni opazoval le šest let, ko je njuno delo prekinil prepir.

Po očetu je Millerja za pianista sprejel tudi Frank Sinatra mlajši, ki ga je Miller spremljal na koncertu v Montrealu, kjer si je zlomil kolk in doživel srčni napad. Njuno sodelovanje je trajalo osem let, v tem času pa je Frank mlajši za enega izmed ameriških medijev sodelavca opisal kot najboljšega pianista, ki je kadar koli spremljal katerega koli pevca.

Prevajalec za Sinatro
Miller je bil za Sinatro več kot le spremljevalec za klavirjem, saj pevec ni znal prav dobro prebirati not, medtem ko mu je pianist pomagal, da je znake na notnem črtovje preoblikoval v nepozabne pesmi. "Ne da Sintra ne bi znal brati not, samo ni jih znal brati prav dobro. To pa je bila stvar, ki jo je moj oče obvladal. Na neki način je prevajal - znal je prebrati prav vse," je očetovo delo pri slavnem pevcu opisala njegova hči Meredith Miller, ki sklepa, da je bilo sodelovanje med glasbenikoma mogoče tudi zaradi njunih različnih značajev; Sinatra je znal biti zelo vihrav, metem ko je Miller njegove izpade sprejemal bolj kot ne mimogrede.

Počitek za klavirjem
"Nikoli ni pri ničemer vztrajal in ni iskal slave. Bil je precej skromen in mislim, da tu tiči razlog, zakaj se je z obema Sinatrama, še posebej s starejšim, tako dobro razumel," je povedala Millerjeva, ki pa je razložila tudi, da njen oče le ni bil vedno tako lahkomiseln - pri delu ni bilo šale. Bill je znal biti strog šef skupini, ki je Sinatro spremljala na koncertih in ki ji je pogosto dirigiral. "Vsa ta leta sem bil njegov spremljevalec, od časa do časa pa kakšno pesem tudi zložim. Igram na obveznih pesmih, kot so balade, kjer je veliko solističnih klavirskih vložkov; včasih pa tudi na dveh ali treh ritmičnih pesmih, da se vsake toliko časa lahko malo usedem," pa je že leta 1970 svoje delo za Sinatro opisal Miller.