Sein Bühnendebüt gab Gedda dann am 8. April 1952 am "Königlichen Theater" von Stockholm mit der Titelrolle des Postillons Chapelou in Adolphe Adams Oper "Der Postillon von Lonjumeau"⁴⁾. Über Nacht wurde der Tenor bekannt, die anschließende Begegnung mit dem großen Produzenten klassischer Musik auf Schallplatten, Walter Legge⁴⁾ (1906 – 1979), der gerade eine Schallplattenproduktion des Mussorgskischen "Boris Godunow"⁴⁾ mit dem großen bulgarischen Bassisten Boris Christoff²⁾ (1914 – 1993) in der Titelrolle plante, förderte Geddas kometenhaften Aufstieg. Die Rolle des "falschen Dimitri" war für den Sänger die Eintrittskarte in die europäische Musikwelt. Schnell machte Nicolai Gedda sich einen internationalen Namen als herausragender lyrischer Tenor seiner Zeit, schon 1952 wirkte er an der Pariser Oper in einer Aufführung des "Oberon"⁴⁾ von Carl Maria von Weber mit, ein Jahr später interpretierte er an der Mailänder "Scala" unter Herbert von Karajan den Don Ottavio in Mozarts "Don Giovanni"⁴⁾.

Der Startenor Gedda reiste von Konzert zu Konzert rund um den Globus, sang mehr als 60 Rollen in Oper, Operette und Oratorium, ohne sich auf ein bestimmtes Fach zu spezialisieren, und hatte rund zweihundert Lieder (Einzelvorträge) in schwedischer, italienischer, deutscher, russischer, französischer und englischer Sprache im Repertoire. Seine Partien alle aufzuführen, würde den Rahmen sprengen, er wurde mit Titelrollen in Mozart-Opern ebenso gefeiert wie als Rossini-Interpret, er dominierte in Opern von Bellini, Donizetti, Verdi, Puccini, Flotow, Lortzing, Bizet, Tschaikowsky oder Offenbach wie in Operetten von Strauß, Millöcker oder Léhar. Seine Stimme hatte dank seiner eigener Einschätzung – er übte immer kluge Zurückhaltung, was seine Rollenplanung anbelangte und überbeanspruchte nie seine Stimme – sowie eiserner Disziplin bis ins Alter Tiefe und Volumen, selbst mit 75 Jahren gab er noch beeindruckende Liederabende. Nicolai Gedda war zweifellos der sprachgewandteste aller berühmten Tenöre des 20. Jahrhunderts: Er beherrscht akzentfrei sowohl Schwedisch, Russisch und Deutsch als auch Italienisch, Französisch und Englisch. Sein Repertoire war dementsprechend riesig (etwa 50 verschiedene Opernpartien) und sein diskographischer Nachlass quantitativ dem der meisten seiner Kollegen weit überlegen ("the world's most recorded tenor").⁵⁾
Zahllose Schallplatten zeugen von Geddas Vielseitigkeit, sei es im "ernsten" Fach oder mit Aufnahmen der sogenannten "leichten Muse", er glänzte in Bachs "h-moll-Messe" ebenso wie in Opern und Operetten und viele seiner Lieder sind bis heute unvergessen. Von der Fachkritik wurde Gedda als "einer der vielseitigsten, stilsichersten und technisch perfektesten Sänger der Nachkriegszeit" bezeichnet.
  
Nicolai Gedda, der 1968 Schweizer Staatsbürger wurde und in einer kleinen Villa in Tolochenaz bei Morges am Genfer See lebt, gab 1983 an der Seite von Kiri Te Kanawa⁴⁾ in Verdis "La Traviata" seine letzte Vorstellung an der "Met". Seine letzte Opernrolle übernahm er Ende Januar 1997 am Londoner "Covent Garden" als Patriarch Abdisu von Assyrien in Pfitzners "Palestrina"⁴⁾, zog sich dann von der Bühne zurück und gab nur noch hin und wieder Liederabende.
Heute lebt der Künstler zusammen mit seiner dritten Frau Aino Sellermark-Gedda in seiner Villa in der Schweiz. Der Künstler war zuvor zwei Mal verheiratet: Seine erste Ehe, die sich bereits nach kurzer Zeit als spannungsreich erwies, hatte er 1953 mit einer Tochter russischer Emigranten geschlossen. Bereits 1954 wollte Gedda sich scheiden lassen, doch erst nach einem langwierigen Prozess, der wegen finanzieller Streitigkeiten rund zehn Jahre andauerte, konnte die Trennung in Frankreich offiziell bestätigt werden. Auch die zweite, überstürzt geschlossene Ehe war wieder geschieden worden.
Am am 11. Juli 2010 feierte der als "Poet unter den Tenören" gefeierte Künstler seinen 85. Geburtstag, das Geheimnis seiner langen Karriere: Disziplin und das Wissen um die Grenzen der Stimme. Vor zu schweren Rollen in jungen Jahren und all zu vielen Auftritten hat er sich gehütet. Das Leben jener Stars, die von Aufführung zu Aufführung jetten, kritisierte er scharf. "Lässt man dies zur Gewohnheit werden, um möglichst viel Geld zu verdienen, verkürzt man seine Karriere um mindestens zehn Jahre", schrieb Gedda in seiner Autobiografie.⁶⁾