Andre Navarra wurde am 13. Oktober 1911 in Biarritz als Kind einer Musikerfamilie geboren. Sehr früh zeigte sich, dass Andre Navarra ein wirkliches Talent zum Violoncello-Spielen hatte und mit 9 Jahren begann er seine Studien am Conservatoire von Toulouse. Mit 11 Jahren gab er sein erstes Konzert. 1924 erhielt er den "premier prix" des Conservatoires de Toulouse. Zu diesem Zeitpunkt entschied er sich, sein Leben der Musik zu widmen und ab 1926 studierte er bei Jules Loeb am Pariser Conservatoire National. Nebenher war er in seiner Jugend weiterhin ein hervorragender Mittelgewichts-Boxer und Schwimmer.
1929, im Alter von 18 Jahren, wurde er Mitglied des Kretly String Quartet, mit dem er 7 Jahre konzertierte. Mit dem Lalo-Konzert gab er 1931 in Paris mit dem Kölner Orchester sein Solo-Debut. 1933 wurde er erster Cellist des Grand Opera Orchesters in Paris. Nach einem ersten Preis beim internationalen Wettbewerb in Wien 1937 begann seine internationale Karriere und er galt schnell als einer der renommiertesten Cellisten. Er wurde Solo-Cellist a der Pariser Opera Comique und Mitglied des "BBN"-Trios.
Während des Zweiten Weltkriegs, von 1939 bis 1945, blieb sein Violoncello im Kasten und er diente in der französischen Infaterie. Nach Beendigung des Weltkriegs setzte er seine Karriere fort und konzertierte mit verschiedenen namhaften europäischen Orchestern. 1949 wurde er Professor am Conservatoire National Supérieur de Musique de Paris als Nachfolger Pierre Fourniers. 1967 wechselte er an die Nordwestdeutsche Musikakademie in Detmold. Nebenher gab er etliche Kurse in Sienna, Wien und London. Viele namhafte Cellisten zählten zu seinen Schülern (Heinrich Schiff, Martin Ostertag, Marcio Carneiro, Johannes Goritzki, Christoph Richter, Friedrich-Jürgen Sellheim, um nur einige zu nennen). Zahlhafte Aufnahmen und Uraufführungen rundeten sein Schaffen ab.