Tbilisziben született 1970-ben, tanulmányait szülővárosában, a Vano Sarajishvili Nemzeti Konzervatóriumban végezte. Már zeneakadémistaként felvételt nyert a Grúz Állami Operaház társulatába, ahol 1996-ban, Az álarcosbál Renatójaként debütált. Számos rangos zenei díj (többek közt a BRAVO 1998, a 2000. évi Leyla Gencer Verseny bariton különdíja, az Ifjú Operaénekesek Jelena Obrazcova Versenyének I. díja, illetve a 2005. évi busettói Voci Verdiane I. díja) birtokosa. Már pályája elején vendégszerepelt a szófiai Nemzeti Operaházban, a frankfurti Operaházban, Szentpétervárott, Isztambulban és Japánban, ahol olyan jeles művészekkel dolgozhatott együtt mint Jelena Obrazcova, Paata Burchuladze, Renato Bruson, Katia Ricciarelli, Alessandra Marc, Kaludi Kaludow, vagy Rost Andrea. A 2005/2006-os évad kezdete óta a weimari Nationaltheater operatársulatának tagja, ám nemrégiben a parmai Teatro Regióban és a valenciai Palau de les Arts színpadán is óriási sikert aratott: Parmában a Rigoletto címszerepében, Valenciában Miller (Verdi: Luisa Miller) szerepében. A Rigoletto címszerepében a New York-i Metropolitan Opera színpadán (2009. február) is hatalmas sikerrel debütált. Gagnidze további programjában a MET-meghívások mellett fontos állomásként szerepel egyebek között San Francisco, Los Angeles, Washington, a milánói Scala, a párizsi Opéra National, a berlini Deutsche Oper vagy a barcelonai Teatro del Liceu. Fontosabb szerepei: Escamillo (Carmen), Jeleckij herceg (Pikk dáma), Enrico (Lammermoori Lucia), Alfio (Parasztbecsület), Tonio (Bajazzók), Scarpia (Tosca), Jochannaan (Salome), Nabucco, Macbeth, Luna gróf (A trubadúr), Germont (Traviata), Renato (Az álarcosbál), Rodrigo (Don Carlos) Hollandi (A bolygó hollandi).