N'Koulou werd gevormd in de Kadji Sports Academy. Hij tekende op zeventienjarige leeftijd contract bij AS Monaco. Na een jaar bij het tweede elftal haalde toenmalig Monaco-coach Ricardo Gomes N'Koulou bij het eerste. Daarvoor speelde hij tussen 2008 en 2011 in totaal 78 wedstrijden. N'Koulou tekende op 29 juni 2011 een vierjarig contract bij Olympique Marseille. Daar vormde hij tijdens het seizoen 2012/13 met Rod Fanni een vast duo centraal achterin.
In de finale van de Afrika Cup 2017 zorgde Nicolas N'Koulou als invaller in de 58ste minuut voor de gelijkmaker tegen Egypte. Door het doelpunt van teamgenoot Vincent Aboubakar won Kameroen voor de vijfde keer de Africa Cup.