diff --git a/src/backend/tcop/backend_startup.c b/src/backend/tcop/backend_startup.c
index 5abf276c89848..a810e41a9040e 100644
--- a/src/backend/tcop/backend_startup.c
+++ b/src/backend/tcop/backend_startup.c
@@ -496,6 +496,7 @@ ProcessStartupPacket(Port *port, bool ssl_done, bool gss_done)
 	ProtocolVersion proto;
 	MemoryContext oldcontext;
 
+retry:
 	pq_startmsgread();
 
 	/*
@@ -616,6 +617,7 @@ ProcessStartupPacket(Port *port, bool ssl_done, bool gss_done)
 #endif
 
 		pfree(buf);
+		buf = NULL;
 
 		/*
 		 * At this point we should have no data already buffered.  If we do,
@@ -634,7 +636,16 @@ ProcessStartupPacket(Port *port, bool ssl_done, bool gss_done)
 		 * another SSL negotiation request, and a GSS request should only
 		 * follow if SSL was rejected (client may negotiate in either order)
 		 */
-		return ProcessStartupPacket(port, true, SSLok == 'S');
+		ssl_done = true;
+		if (SSLok == 'S')
+		{
+			/*
+			 * We are done with SSL and negotiated correctly, so consider the
+			 * same for GSS.
+			 */
+			gss_done = true;
+		}
+		goto retry;
 	}
 	else if (proto == NEGOTIATE_GSS_CODE && !gss_done)
 	{
@@ -672,6 +683,7 @@ ProcessStartupPacket(Port *port, bool ssl_done, bool gss_done)
 #endif
 
 		pfree(buf);
+		buf = NULL;
 
 		/*
 		 * At this point we should have no data already buffered.  If we do,
@@ -690,7 +702,16 @@ ProcessStartupPacket(Port *port, bool ssl_done, bool gss_done)
 		 * another GSS negotiation request, and an SSL request should only
 		 * follow if GSS was rejected (client may negotiate in either order)
 		 */
-		return ProcessStartupPacket(port, GSSok == 'G', true);
+		gss_done = true;
+		if (GSSok == 'G')
+		{
+			/*
+			 * We are done with GSS and negotiated correctly, so consider the
+			 * same for SSL.
+			 */
+			ssl_done = true;
+		}
+		goto retry;
 	}
 
 	/* Could add additional special packet types here */
diff --git a/src/test/postmaster/meson.build b/src/test/postmaster/meson.build
index d2709867da71c..fa30883b601bd 100644
--- a/src/test/postmaster/meson.build
+++ b/src/test/postmaster/meson.build
@@ -9,6 +9,7 @@ tests += {
       't/001_basic.pl',
       't/002_connection_limits.pl',
       't/003_start_stop.pl',
+      't/004_negotiate.pl',
     ],
   },
 }
diff --git a/src/test/postmaster/t/004_negotiate.pl b/src/test/postmaster/t/004_negotiate.pl
new file mode 100644
index 0000000000000..949aa2ba19ac0
--- /dev/null
+++ b/src/test/postmaster/t/004_negotiate.pl
@@ -0,0 +1,83 @@
+# Copyright (c) 2026, PostgreSQL Global Development Group
+
+# Test the negotiation of combined SSL and GSS requests.  This test
+# relies on both SSL and GSS requests to be rejected first, followed
+# by more requests.
+
+use strict;
+use warnings FATAL => 'all';
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+use Test::More;
+use Time::HiRes qw(usleep);
+
+my $node = PostgreSQL::Test::Cluster->new('main');
+$node->init;
+$node->append_conf('postgresql.conf', "log_min_messages = debug2");
+$node->append_conf('postgresql.conf',
+	"log_connections = 'receipt,authentication,authorization'");
+$node->append_conf('postgresql.conf', 'trace_connection_negotiation=on');
+$node->start;
+
+if (!$node->raw_connect_works())
+{
+	plan skip_all => "this test requires working raw_connect()";
+}
+
+my $sock = $node->raw_connect();
+
+# SSLRequest: packet length followed by NEGOTIATE_SSL_CODE.
+my $ssl_request = pack("Nnn", 8, 1234, 5679);
+
+# GSSENCRequest: packet length followed by NEGOTIATE_GSS_CODE.
+my $gss_request = pack("Nnn", 8, 1234, 5680);
+
+# Send SSLRequest, reject or bypass.
+$sock->send($ssl_request);
+my $reply = "";
+$sock->recv($reply, 1);
+if ($reply ne 'N')
+{
+	$sock->close();
+	plan skip_all =>
+	  "server accepted SSL; test requires SSL to be rejected";
+}
+
+# Send GSSENCRequest, reject or bypass test.
+$sock->send($gss_request);
+$reply = "";
+$sock->recv($reply, 1);
+if ($reply ne 'N')
+{
+	$sock->close();
+	plan skip_all =>
+	  "server accepted GSS; test requires GSS to be rejected";
+}
+
+my $log_offset = -s $node->logfile;
+
+# Send a second SSLRequest, now that we know that both SSL and GSS have
+# been rejected for this connection.  We are done with both requests, so
+# extra requests will be rejected and fail with an invalid protocol
+# version, and the connection should be closed by the server.
+$sock->send($ssl_request);
+
+# Try to read a response, there should be nothing, and certainly not an
+# extra 'N' message indicating a rejection.
+$reply = "";
+my $bytes = $sock->recv($reply, 1024);
+isnt($reply, 'N',
+	"server does not re-enter SSL negotiation after SSL+GSS were both tried");
+
+$sock->close();
+$node->wait_for_log(qr/FATAL: .* unsupported frontend protocol 1234.5679/,
+					$log_offset);
+
+# Check extra connection with a simple query.
+my $result = $node->safe_psql('postgres', 'select 1;');
+is($result, '1', 'server able to accept connection');
+ok($node->is_alive(), "server still running after negotiation attempt");
+
+$node->stop;
+
+done_testing();