W roku 1956 muzyk przeprowadził się do Vancouver w stanie Washington. Tam też rozpoczął muzyczną karierę nagrywając utwór „Lumberjack”, którego autorem był Leon Payne. singel sprzedał się całkiem dobrze, lecz nie wpłynął zbyt znacznie na rozwój kariery Nelsona. Piosenkarz kontynuował prace jako spiker radiowy w Vancouver i nadal śpiewał w klubach. Sprzedał za 100 dolarów utwór „Family Bible”. Nabywcą był Claude Gray – muzyk country, dla którego w 1960 roku piosenka okazała się być dużym hitem. „Family Bible” była też wielokrotnie nagrywana przez różnych muzyków, a także często jest uważana za klasyka z rodzaju muzyki gospel.

Jako popularny tekściarz W 1960 Nelson przeniósł się do Nashville w stanie Tennessee, lecz miał problem z podpisaniem kontraktu z wytwórnia płytową. Po dłuższym czasie udało mu się jednak podpisać umowę z firmą Pamper Music. Po tym jak Ray Price nagrał stworzoną przez Nelsona piosenkę „Night Life” (podobno najczęściej coverowaną piosenkę country;