Anticamente il paese veniva chiamato "Pauli Gerrei". In latino "Pauli" significa palude(in quanto  in passato le acque, non avendo scolo, ristagnavano, dando origine ad una palude) e la parola "Gerrei", di probabile origine mesopotamica, significa passaggio(poichè in passato la zona era luogo di passaggio per i ladri di bestiame).

I primi insediamenti risalgono al periodo nuragico, come attestano il pozzo sacro di " Su Musuleu", in cui furono ritrovate due lance in bronzo e la base di una statua, e di "Is Mulineddus" e di probabili circoli megalitici in località "Mont'Ixi".

Al periodo punico e romano risalgono: 

• un ripostiglio di monete imperiali, ritrovato in regione "Spigniau", 

• due sarcofagi in marmo rappresentanti delle muse, 

• un frammento di una colonna in bronzo con un'iscrizione trilingue del II sec. A.C. (in punico-latino-greco), in cui un devoto, Cleone, dedica un altare in bronzo come ringraziamento per un'avvenuta guarigione, al signore "Eshumum Merre"corrispondente alla divinità salutifera greca Asclepio e romana Esculapio, ritrovata in località "Santu Jacci" (oggi esposta presso l'Accademia delle Scienze di Torino).

Sempre in questa zona sono stati ritrovati: 

• frammenti di stoviglie di ogni genere e di ogni età, ma principalmente dell'epoca nuragica sino ad il periodo romano, 

• un frammento di statuetta rappresentante Cerere 

• molte monete puniche. 

Nella zona di "Bingia Manna" furono scoperte due tombe con due scheletri coperti di lastre e dentro le tombe vasi oggetti in bronzo e in filo d'argento (Museo Archeologico di Cagliari). La mancanza d'iscrizioni e monete non permette di datare in modo preciso tali oggetti; si presume risalgano alla fine dell'età imperiale. 

Nel Medioevo il paese apparteneva al Giudicato di Cagliari e fece parte della Curatoria del Gerrei con il nome di Pauli Gerrei. In seguito passò ai Pisani e quindi agli Aragonesi: di questo periodo resta una casa chiamata ancora oggi "Sa dommu de su Marchesu" e una campagna "Sa tanca de su Marchesu", che testimoniano la presenza di un marchese nel paese o più probabilmente di un podatario, cioè il fattore che curava i beni e gli interessi del marchese. Nel 1681 fu incorporato nella Contea di Villasalto, feudo della famiglia aragonese degli Zatrillas, che abitò nel palazzo baronale di Pauli fino al 1806 quando l'ultimo discendente di quella casa, il marchese Don Francesco si trasferì a Cagliari dove morì il 27 settembre 1814 senza lasciare discendenti. La villa passò ai Vivaldi Pasqua, marchesi di Villaclara, dai quali fu riscattata nel 1839. Successivamente il territorio del feudo passò al demanio dello Stato e da questo ai comuni. Il 12 dicembre 1863 con un Decreto Regio il nome del paese fu tramutato in San Nicolò Gerrei in onore di San Nicola di Bari in onore del paese. 

All'indomani dell'Unità d'Italia a causa  di una crisi economica gli abitanti di San Nicolò conobbero il fenomeno dell'emigrazione all'estero soprattutto Germania, Belgio, Francia ed America. 

Agli inizi del '900 San Nicolò Gerrei veniva considerato il centro più importante  del Gerrei, poiché fungeva da porta viaria ed amministrativa. Vi erano infatti la Pretura, il Carcere, la Scuola, l'Ufficio Telegrafico, il Consorzio Sanitario e quello Veterinario. Nel 1969 è nato il Consorzio Caseario del Gerrei, nel 1982 è stata istituita la Biblioteca, nel 1988 l'Associazione turistica "Pro-Loco", nel 1989 la Cooperativa Agricola de "Su Niu de S'Achili" e a metà anni novanta la Cooperativa "Sa Tiria".