Figlio di un ebanista di origini bretoni, fu incoraggiato ad intraprendere lo studio del violoncello dal padre Joseph e dalla madre Marguerite Boura, entrando al Conservatorio di Parigi all'età di dodici anni. Studiò violoncello, prima con Louis Feuillard e poi con Gérard Hekking. Vinse il primo premio di violoncello al conservatorio all'età di sedici anni, e poi studiò armonia con Jean Gallon. Fece il suo debutto con Orchestre Lamoureux nel 1931 all'età di diciassette anni, eseguendo il concerto per violoncello e orchestra di Édouard Lalo.
Nel 1935 entrò a far parte della Montecarlo Philharmonic Orchestra, come primo violoncello, e vi rimase fino al 1937. Venne diretto da Bruno Walter e Arturo Toscanini, ed eseguì la parte solistica del Don Qixote sotto la direzione del compositore Richard Strauss. Questo pezzo divenne il suo emblema e venne da lui eseguito moltissime volte oltre ad essere inciso su disco.
Nel 1937 passò alla Boston Symphony Orchestra sotto la direzione di Serge Koussevitsky, come primo violoncello fino al 1940. Nel 1938 iniziò la carriera da solista alla Boston's Town Hall, accompagnato da Leonard Shure. Fu primo violoncello dell'Orchestre de la Société des Concerts du Conservatoire di Parigi nel periodo 1946–1947. Nel 1947 debuttò in Inghilterra con Beecham, sempre in Don Quixote al Festival di Richard Strauss a Londra. "Mio ragazzo" gli disse Beecham, "avrai successo in Inghilterra perché hai temperamento". Nel 1950 Tortelier venne scelto da Casals come primo violoncello per la Prades Festival Orchestra. Tortelier era convinto che, fra tutti i violoncellisti, fosse stato Casals ad aver avuto maggior influenza su di lui. Un critico francese scrisse di lui: "Se Casals è Giove, Tortelier è Apollo." Tortelier suonò nei Peabody Mason Concert a Boston nel 1952.[2]
Anche se era cattolico, Tortelier fu ispirato dagli ideali dei fondatori dello stato di Israele nel 1948, e negli anni 1955-1956 trascorse qualche tempo, con la moglie e i due figli, nel kibbutzMaabarot, nei pressi di Netanya.
Le sue composizioni comprendono un concerto per due violoncelli e orchestra (1950), una suite per violoncello solo in Re, e due sonate per violoncello e pianoforte. Ha scritto anche una serie di variazioni per violoncello e orchestra (Possa la music portare la pace). Ha anche scritto una sinfonia, Israel Symphony, dopo la sua esperienza di vita in kibbutz. La sua esecuzione della Cello Suite di Bach è stata pubblicata da Galliard nel 1966.
Ebbe come allieva Jacqueline du Pré quando frequentò brevemente le sue lezioni al Conservatorio di Parigi, anche se non era il suo insegnante principale (che era William Pleeth). Altri suoi allievi sono stati Arto Noras, Nathan Waks e Raphaël Sommer. Nel 1970 ha tenuto una serie di master class che sono state registrate e trasmesse alla televisione dalla BBC, dalle quali emerge il suo stile molto dinamico di suonare.
Fra i suoi interessi vi erano la bicicletta e il flauto. Oltre a suonare il violoncello, fu anche direttore d'orchestra, come il suo collega russo Mstislav Rostropovich. Anche se a volte si attribuisce erroneamente a Rostropovich, fu Tortelier ad introdurre il puntale del violoncello piegato, che consentiva l'utilizzo dello strumento più in orizzontale che in verticale.[3]
Paul Tortelier si sposò due volte. Prima con Madeleine Gaston, dalla quale divorziò nel 1944, e poi con Maud Monique Martin (anche lei violoncellista). Suo figlio Yan Pascal Tortelier è un direttore d'orchestra e sua figlia Maria de la Pau una pianista. Morì all'età di 76 anni a Villarceaux Yvelines, vicino a Parigi.
Tortelier ritirò i figli dalla scuola formale, in modo che potessero concentrarsi sulla musica. Quando durante un'intervista con Huw Wheldon alla televisione britannica, gli fu chiesto se non ci fossero autorità in Francia che obbligassero a mandare i figli a scuola, egli rispose: Non voglio sapere niente di tutte le autorità, sono un solista ed essi saranno dei solisti. E quando Wheldon gli chiese ma cosa succede se non diventeranno dei solisti? con una certa sorpresa, Tortelier disse: Beh, se inizi a pensare a cosa accadrà se non riesci, non farai mai niente.