Paul Walden grew up in a large musical family, by the banks of the Whanganui River. His father, Ben Tamatea Walden, was a talented singer, pianist, dancer and juggler and tutored his four children. By the age of four Walden was singing on stage with his twin brother and his two sisters, mainly hymns and traditional Māori music.
After leaving secondary school Walden joined his sister Mary's dance band in Wellington, where he soon came to the notice of radio stations 2ZB and 2YA, who placed him on several radio shows.