Der bekannteste Sinneswandel Laxness' war seine Abrechnung mit Stalin und der Sowjetunion in seinem Buch Zeit zu schreiben von 1963. "Es ist lehrreich zu beobachten, wie Stalin mit jedem Jahr mehr ein Schulbeispiel wurde, wie die Macht die moralische Kraft aus den Menschen saugt, so daß ein Mann, der vollkommene Allmacht innerhalb seiner Umgebung erlangt hat, gleichzeitig gänzlich unmoralisch geworden ist", heißt es darin (S. 215). Das Buch weckte bei seinem Erscheinen ungeheures Aufsehen, doch aus dem Rückblick wird erkennbar, wie sich Laxness' Einstellungen die ganzen fünfziger Jahre hindurch änderten.
Mit den Glücklichen Kriegern (1952) schrieb er eine neue "Isländersaga", die auch im Sagazeitalter angesiedelt ist. Darin karikierte er das alte Heldenethos der Isländersagas, die Botschaft des Romans richtete sich aber nicht weniger an die Gegenwart, denn der Glaube an Macht und Gewalt sei seit langem ultima ratio jener Machthaber, die nichts mehr fürchteten als ihre eigenen Untertanen. Wer wollte, konnte darin Seitenhiebe auf Hitler und Stalin und den Führerkult überhaupt sehen, das Buch enthielt sogar ein Gegenbild gegen jene Gesellschaften, in denen starke Führer oder Diktatoren herrschten; der Autor fand es bei den grönländischen Inuit. Dieses Naturvolk kenne es nicht anders, als daß alle gleich seien, in Frieden und Eintracht miteinander lebten und keine Führer hätten.
1960 erschien Das wiedergefundene Paradies. Die Hauptperson, der Bauer Steinar, bekommt eine Vision vom Paradies auf Erden. Er macht sich auf, es zu finden, kehrt aber am Ende der Handlung auf den heimatlichen Hof zurück: Das Gerede vom Tausendjährigen Reich war nichts als eine hohle Phrase. Am Ende sieht es so aus, als sei nie etwas geschehen, als stünde Steinar unverändert genauso da wie vor seinem Aufbruch. Laxness selbst sagte in einem Artikel über die Entstehung des wiedergefundenen Paradieses:
"Ein kluger Mann hat einmal gesagt, wer fortgeht, kommt niemals zurück, und das liegt daran, daß man bei einer Rückkehr ein anderer Mensch ist als der, der irgendwann aufbrach... Und zwischen der Hauswiese, auf der man losging, und der, auf der man wieder ankommt, liegen nicht nur Königreiche und die Ozeane und Wüsten der Welt, sondern das verheißene Land selbst."
Steinar findet einen Glauben oder eine Vision, die er wieder verliert, doch am Ende stößt er zu einer neuen Sicht der Welt vor. Das Gleiche läßt sich von Halldór Laxness sagen. Der Sowjetsozialismus erwies sich nicht als das Paradies, für das er ihn gehalten hatte.
Wie sich an seinen Werken ablesen läßt, änderten sich Laxness Überzeugungen im Lauf der Jahre. Und doch kehren von der frühesten Zeit bis zu den letzten Artikeln bestimmte grundlegende Züge in seinen Werken immer wieder. Er sah die Dinge aus einem anderen Blickwinkel als andere, formulierte oft sehr scharf und kritisch, konnte seinen Figuren und ihren Handlungen jedoch immer auch komische Seiten abgewinnen. Stets galt sein Mitgefühl den Schwachen. All seine Werke sind ein Lobgesang auf das Verborgene Volk, wie er es nennt, und darunter verstand er nicht die in der Natur lebenden Wesen aus dem isländischen Volksglauben, sondern die kleinen, einfachen Leute. Die Achtung vor diesen einfachen Menschen macht den Kern von Halldór Laxness Werken aus.