A San Martínban született Nicolás Gaitán 13 évesen került a Boca Juniors utánpótlás akadémiájára.[2]2008. június 1-jén debütált egy Arsenal Sarandí elleni mérkőzésen.[3] Első góljait két hónappal később szerezte, a Huracán csapatának talált be kétszer.[4]
Bemutatkozott a nemzetközi porondon is, szeptember 28-án szerezte első gólját a Copa Sudamericánában az ecuadori LDU Quitónak talált be.[5] Utolsó szezonjában 33 bajnokin hétszer volt eredményes, a Boca az Aperturát a 11., a Clausurát a 16. helyen zárta.
Benfica
2010. május 3-án írt alá a Benfica csapatához, a portugál csapat 8,4 millió eurót fizetett a játékjogáért,[6] és akik a Real Madridhoz szerződő Ángel Di María utódjának szánták.[7]Óscar Cardozo után ő lett a lisszaboniak történetének második legdrágábban vásárolt játékosa. Első idényében minden tétmérkőzést figyelembe véve 48-szor lépett pályára és kilenc gólt szerzett.
A 2010-2011-es idény végén jelölték az év játékosa díjra.[8] a következő idényben pedig a nemzetközi kupaporondon szerepelt nagyszerűen csapatával, a Bajnokok Ligájában a tavaszi kieséses szakaszba jutottak.[9] A 2013-2014-es bajnokságban összesen 26 mérkőzésen hat góllal segítette bajnoki címhez a Benficát és a Rio Ave elleni kupadöntőt is az ő gólja döntötte el.[10] 2014. augusztus 31-én az ősi rivális Sporting CP elleni bajnoki után a mérkőzés emberének választották.[11]
2014 novemberében meghosszabbította a szerződését 2018 nyaráig.[12]2015. szeptember 30-án góllal segítette csapatát az Atlético Madrid elleni győzelemhez.[13] December 9-én új, 2019 nyaráig szóló szerződést írt alá, a kivásárlási árát pedig 45 millió euróban határozta meg a klubja.[14]2016. március 9-én az ő góljának is köszönhetően a Benfica a Zenyiten túljutva a legjobb nyolc közé jutott a Bajnokok Ligájában.[15] Május 15-én két gólt szerzett a Nacional ellen, csapata pedig bebiztosította az újabb bajnoki címet. Az utolsó bajnoki fordulóban lecserélésekor a hazai közönség felállva ünnepelte, ő pedig könnyek közt hagyta el a pályát. A mérkőzés után elismerte, hogy ez volt az utolsó mérkőzése a Sasok mezében.[16][17]
2018. február 26-án a kínai élvonalban szereplő Talien Jifang szerződtette.[22][23] Március 3-án, a Sanghaj SIPG ellen 8–0-ra elveszített bajnokin mutatkozott be új csapatában.[24] 2018. március 16-án, a Peking Kuan elleni mérkőzésen egy párharc során ütközött és átmenetileg elveszítette az eszméletét.[25] 2018. április 7-én az első gólját is megszerezte a kínai bajnokságban a Csungking Lifan elleni 2–2-es hazai mérkőzésen.[26]
2020. január 31-én aláírt a franciaLille OSC csapatához.[28] Itt mindössze 4 találkozón játszott.[29]
Braga
2020 augusztusában bejelentették, hogy visszatér Portugáliába és az SC Braga csapatában fog szerepelni. Gaitán 1 éves szerződést írt alá, amely különböző feltételek teljesülése esetén meghosszabbodhat.[1] Egy korábbi sérülése miatt október 25-én ugyan már ott volt a keretben a Guimaraes ellen, de nem lépett pályára.[30] Október 29-én mutatkozott be és gólt is szerzett az ukrán Zorja Luhanszk elleni 2–1-re megnyert Európa-liga meccsen.[31]
Peñarol
2021 nyarán az uruguayi Peñarol csapatához igazol, majd a szezon végén bajnoki címet ünnepelhetett a csapattal.[32][33]
Paços Ferreira
2022. január 31-én félévre a Paços Ferreira csapatába igazolt, további egy éves hosszabbítási opcióval.[34]
Pályafutása kezdetén leginkább a középpályás sor bal szélén játszott, miután a Benfica leigazolta a portugál csapatnál a középpálya bármely pontján bevethető játékos lett belőle.
Gaitán bal lábas, azonban képes a jobb szélen is játszani. Labdabiztos játékos, akinek a legfőbb erénye a megszerzett labdák megtartása, elosztása.[38][39]