Zur gleichen Zeit wie Gunther und Sigfrid lebte auch eine Königin, die viele Männer begehrter. Sie hieß Brunhild und herrschte über Island. Brunhild war eine gestrenge Frau, die hohe Ansprüche an ihren zukünftigen Gatten stellte – er musste sie nämlich in drei sportlichen Disziplinen besiegen können, sonst hätte er keine Chance bei ihr und war des Todes.
Zu ihren eifrigsten Verehrern gehörte Gunther, König zu Worms. Und so sagte dieser eines Tages zu Sigfrid: „Wenn du mir hilfst, Brunhild für mich zu gewinnen, so werde ich auf immer meine Ehre und mein Leben für dich wagen!“ Diese Gelegenheit kam für Sigfrid nur zu günstig. Er versicherte schnell, dass er Gunther helfen wolle, und forderte für seine Hilfe die Hand der schönen Kriemhild. Damit war Gunther gleich einverstanden – würde er Brunhild heiraten können, so würde Kriemhild Sigfrids Frau.
Gemeinsam mit Hagen von Tronje und dessen Bruder Dankwart fuhren die beiden Männer nach Island. Zwölf Tage und Nächte waren die Reisenden unterwegs, bis sie an der Burg Isenstein ankamen. Dort geleitete Sigfrid den König und sein Pferd wie ein Lehnsmann von Bord des Schiffes. Brunhild begrüßte ihre Gäste sehr freundlich. Zunächst Sigrid, den sie ja schon kannte, dann König Gunther.
Schon am kommenden Tag fand der Wettkampf in den Disziplinen Speerwurf, Steinschleudern und im Sprung statt. Obwohl König Gunther von stattlicher Statur war, hatte er keine Chance gegen die starke Königin der Isländer. Doch dafür hatte Gunther ja Sigfrid mit auf die Reise genommen. Der hatte nämlich die Tarnkappe aufgesetzt und führte nun alle Übungen an Stelle von Gunther durch, der wiederum nur so tat, als würde er die Bewegungen machen.
Brunhild war so stark, dass sie alleine ein Schild tragen konnte, dass zuvor vier Männer in die Arena hatte tragen müssen. Als sie den Speer schleuderte, da geschah das so heftig, dass die Waffe durch den Schild von Gunther drang und den unsichtbaren Sigfrid am Mund verletzte. Doch Sigfrid besann sich sofort auf seiner Aufgabe, schleuderte den Speer mit eben solcher Wucht zurück, dass Brunhild nun zu Boden stürzte. Die erste Disziplin hatten die Männer für sich entscheiden können.
Doch die tapfere Königin rappelte sich sofort wieder auf, nahm einen Stein und schleuderte ihn zwölf Klafter weit, was immerhin rund 22 Meter sind. Wäre es ein kleiner Stein gewesen, so hätte man die Weite sicherlich noch nachvollziehen können, doch es war ein gewaltiger Brocken, den die Königin da schleuderte.
Aber auch bei der zweiten Disziplin standen die Männer der Königin in nichts nach! Der Stein, den Sigfrid für Gunther warf, flog noch ein kleines Stückchen weiter als der von Brunhild – also konnten die beiden auch den zweiten Wettkampf für sich entscheiden. Und auch beim Wettsprung, bei dem Sigfrid - unsichtbar und durch die Kraft der Tarnkappe zusätzlich gestärkt - Gunther mit sich tragen konnte, landete er eine Nasenlänge vor Brunhild. Als diese sich geschlagen sah, forderte sie ihr Volk auf, dem neuen König an ihrer Seite zu huldigen.
So gelang es also König Gunther, die begehrte Brunhild zu sich in sein Reich zu führen. In Worms angelangt, wurde gleich eine prächtige Doppelhochzeit gefeiert, denn natürlich hielt Gunther sein Versprechen ein, seine Schwester Kriemhild Sigfrid zur Frau zu geben. Das jedoch sorgte bei Brunhild für mächtig viel Aufregung und Tränen, denn sie verstand rein gar nicht, warum ihr Mann seine Schwester einem Lehnsmann – denn dafür hielt sie Sigfrid ja – zur Frau gegeben hatte.
Der König versuchte seine Frau zu beschwichtigen, doch es half alles nichts, Brunhild blieb skeptisch und fragte sich innerlich, ob denn bei der Brautwerbung wohl alles mit rechten Dingen zugegangen sei. In der Hochzeitsnacht dann kam es zum Eklat: Als König Gunther versuchte sein Weib zu umarmen, da fesselte Brunhild ihn an Händen und Füßen und hängte den wehrlosen Mann an einem starken Nagel an die Wand. Dort musste er bis zum nächsten Morgen ausharren.
Obwohl Gunther peinlich berührt war, erzählte er sogleich Sigrid von der schändlichen Tat seiner Frau. In der folgenden Nacht stand Sigfrid dann – wieder mit der Tarnkappe ausgerüstet – Gunther bei seinem Eheweib zur Seite. Zum Beweis seiner Tat nahm er heimlich Brunhilds Gürtel und einen Ring, der er ihr bei der Rangelei unbemerkt vom Finger gezogen hatte, an sich.
Kurze Zeit später war das Gastspiel Sigfrids in Worms vorbei. Mit seiner jungen Frau kehrte er nach Xanten zurück und bestieg den Thron seines Vaters.