By the age of fifteen, he had the ability to accompany leading musicians at nightclubs, working regularly at Copenhagen's Jazzhus Montmartre, after his debut there on New Year's Eve 1961, when he was only 15.

When seventeen, he had already turned down an offer to join the Count Basie orchestra, mainly because he was too young to get legal permission to live and work as a musician in the United States.

During the 1960s, Pedersen played with a series of other important American jazzmen who were touring or resident in Denmark, including Ben Webster,[4] Brew Moore, Bud Powell, Count Basie, Roy Eldridge, Dizzy Gillespie, Jackie McLean, and vocalist Ella Fitzgerald.

[5] His predecessor, Ray Brown, thought highly of the Dane and regarded him as the only upright bassist equal to the task of keeping up with the pianist.

A duo performance with Rune Gustafsson at Vossajazz 1980, concluded on the album Just The Way You Are on the label Sonet Gramofon, recorded half a year after this first meeting.

[1] Oscar Peterson wrote: After hearing this phenomenal talent on bass, I realized that somehow, someday we should meet, thereby giving me the opportunity to also play with him.