Gonnostramatza ha sicuramente origini nuragiche di cui si trovano le tracce nel territorio. La zona geografica nella quale insiste il territorio di Gonnostramatza è denominato "Marmilla", derivato dalla conformazione geologica fatta, appunto, a "mammille" cioè di dolci colli simili a mammelle. Le origini nuragiche sono confermate dagli insediamenti presenti e dalla scoperta di reperti scientificamente rilevanti. Tra questi reperti spicca il più antico monile d'oro della Sardegna: il collier della tomba eneolitica di Bingia 'e Monti, che era parte del corredo funerario di un pastore-guerriero della cultura del Campaniforme, di circa quattromila anni fa. La tomba di Bingia 'e Monti è costituita da una ampia nicchia rettangolare scavata nella roccia sedimentaria, alla quale si addossa un ambiente quadrangolare delimitato da quattro grandi pietre poste verticalmente con pareti in muratura a secco. La struttura funeraria è stata utilizzata in un primo momento dalle genti appartenenti alla Cultura eneolitica di Monte Claro e successivamente nell'ambito dell'aspetto campaniforme e della Cultura di Bunnannaro. Nei livelli campaniformi più bassi sono state individuate tre strutture a cista litica sigillate da lastroni calcarei contenenti resti scheletrici umani riferibili a più individui. Sopra le lastre di copertura delle ciste erano stati deposti altri defunti accompagnati da elementi di corredo di particolare pregio rappresentati da reperti ceramici, oggetti in metallo, in pietra, in osso, e da elementi di ornamento tra i quali si distingue il collier d'oro. Si tratta di un oggetto esclusivo che doveva essere riservato a una persona di elevato rango sociale all'interno della comunità e che quindi doveva assumere la valenza di status symbol. Fino al XVII secolo era il centro piu' popolato ed importante della Marmilla, e, dall'XI secolo, sede di capoluogo della Parte Montis inclusa nel Giudicato di Arborea. Tanto importante che Eleonora d'Arborea nel 1388 sceglie Gonnostramatza come sede per la stipula del trattato di pace con Pietro IV d'Aragona con l'intervento dei rappresentati di tutti i borghi del circondario. Del Regno di Arborea seguì tutte le sorti: dal Marchesato di Oristano fu annesso alla Contea di Quirra (1478 a seguito della sconfitta di Leonardo d'Alagon); Il Marchese di Nules ne prese possesso nel 1504 e nel 1675 fu' possesso del Duca di Gandia Francesco Borgia. Le faide familiari all'interno del Marchesato di Nules fecero in modo che nel 1798 il possesso di Gonnostramatza fosse affidato a Filippo Carlo Maria Osorio de La Cueva Castelvi. Gonnostramatza, probabilmente come quasi tutta la Sardegna, ha subito le influenze e le invasioni barbariche comprese quelle di Turchi e Mori, accomunata in queste alla Sicilia ed alla Spagna. Durante le razzie barbariche moltissimi villaggi della zona furono distrutti: tra questi Uras. La "villa" di Uras fu' distrutta nel 1515 da Turchi e Mori. Il pirata che comandava i mori era il famoso e temuto Khair ad-din, detto Barbarossa forse dal nome del fratello Baba Urug. Nella chiesa campestre di San Paolo è murata la lapide che ricorda una della più nefaste incursioni barbaresche del XVI secolo: "El V de arbili MCXV esti istada isfata sa vila de Uras de manu de turcus e morus effudi capitanu de morus Barbarossa". Sérzela fu' definitivamente abbandonata dopo il 1775, per inedia e per decreto di Mons. Pilo, e i suoi abitanti si trasferirono a Gonnostramatza. Nel periodo fascista a Gonnostramatza furono annesse le frazioni di Gonnoscodina e Simala.Gonnostramatza passa dalla provincia di Cagliari a quella di Oristano nel 1975 con l'istituzione della nuova provincia.