Der Ort Güssing wurde im Jahre 1157 erstmals urkundlich erwähnt. Aber zahlreiche Funde aus der Steinzeit bis in die Zeit der Römer weisen auf eine sehr frühe Besiedelung des Gebietes um Güssing hin. In den Gängen des Güssinger Franziskanerklosters sind noch einige Fundstücke aus der Römerzeit zu sehen. Ungarische Quellen berichten, dass die beiden Brüder Wolfer und Hedrich (aus dem steirischen Wildon, andere Historiker meinen aus Hainburg) um 1150 in die Gegend von Güssing kamen und auf dem Vulkankegel, der den Namen "Kyscen" trug, eine hölzerne Burg und ein Kloster (Benediktiner) errichteten. Der Name für den Burgberg "Kyscen" oder lateinisch auch Quizin bedeutet "Wasserburg" oder "Wasserberg" und deutet auf die Lage des Burgberges hin, der damals noch von einer Sumpflandschaft umgeben war.
Der ungarische König Bela III. entzog die Burg schließlich den Besitzern aufgrund ihrer strategischen Lage und erbaute eine feste Burg aus Stein und Ziegel. Die Burg Güssing hieß seither "Novum Castrum" (= Neue Burg, davon leitet sich auch der ungarische Name für Güssing ab Nemeth Ujvár oder auch der kroatische Name Novi Grad).
In den darauffolgenden Jahrhunderten wechselten die Besitzer der Burg mehrmals. Erwähnenswert ist, dass im Jahre 1459 Kaiser Friedrich III. auf Burg Güssing zum ungarischen König gewählt wurde.
Im Jahre 1524 kam Burg Güssing in den Besitz der ungarischen Magnatenfamilie Batthyány, die von nun an das weitere Schicksal der Burg und der Stadt Güssing bestimmten.

Die Siedlung am Fuße des Burgberges hat sich ab dem 15.Jhdt. entwickelt. Seit dem 16.Jhdt. war Güssing freie Stadt mit vollem Stadtrecht (ging später wieder verloren). Unter dem Einfluss der Grafen Batthyány kamen bedeutende Persönlichkeiten nach Güssing wie z.B. der berühmte Botaniker Carolus Clusius oder der Buchdrucker Manlius. Die Batthyánys waren es auch, die das Franziskanerkloster Güssing mit seiner wertvollen Bibliothek gegründet haben. Unter der Franziskanerkirche befindet sich die Familiengruft.
Die Burg Güssing war bis 1870 im Familienbesitz der Batthyány, seither ist sie im Besitz der "Fürst Philipp Batthyányschen Stiftung". Im 19.Jhdt. ging durch Heirat ein großer Teil der Herrschaft Güssing in den Besitz der gräflichen Familie Draskovich über, die zahlreiche kulturelle und wirtschaftliche Impulse für die Stadt gesetzt hat, unter anderem auch die Elektrifizierung der Stadt. Die Gründung des E-Werkes geht auf Graf Draskovich zurück.
Im Jahr 1899 wurde die Bahnlinie Güssing - Körmend eröffnet, diese Bahnlinie wurde jedoch in den 1940er Jahren wieder eingestellt.
1973 wurde die Marktgemeinde Güssing zur Stadt erhoben.