diff --git a/quiche/quic/core/quic_connection.cc b/quiche/quic/core/quic_connection.cc
index d6e2fa1..72bf8c9 100644
--- a/quiche/quic/core/quic_connection.cc
+++ b/quiche/quic/core/quic_connection.cc
@@ -1174,13 +1174,13 @@
                    last_flow_label_received_) {
       if (expect_peer_flow_label_change_) {
         expect_peer_flow_label_change_ = false;
+        QUIC_CODE_COUNT(quic_detected_expected_flow_label_change);
       } else if (header.packet_number > GetLargestReceivedPacket() + 1) {
         // This packet introduced a packet number gap and came with a new flow
         // label so the peer is RTO'ing. In response, send a different flow
         // label.
-        uint32_t flow_label;
-        random_generator_->RandBytes(&flow_label, sizeof(flow_label));
-        set_outgoing_flow_label(flow_label);
+        GenerateNewOutgoingFlowLabel();
+        QUIC_CODE_COUNT(quic_generated_new_flow_label_on_flow_label_change);
       }
       last_flow_label_received_ = last_received_packet_info_.flow_label;
     }
@@ -2926,6 +2926,12 @@
   return direct_peer_address_ != last_received_packet_info_.source_address;
 }
 
+void QuicConnection::GenerateNewOutgoingFlowLabel() {
+  uint32_t flow_label;
+  random_generator_->RandBytes(&flow_label, sizeof(flow_label));
+  set_outgoing_flow_label(flow_label);
+}
+
 bool QuicConnection::ProcessValidatedPacket(const QuicPacketHeader& header) {
   if (perspective_ == Perspective::IS_CLIENT && version().HasIetfQuicFrames() &&
       direct_peer_address_.IsInitialized() &&
@@ -4198,10 +4204,9 @@
                                               clock_->Now());
     }
     if (enable_black_hole_avoidance_via_flow_label_) {
-      uint32_t flow_label;
-      random_generator_->RandBytes(&flow_label, sizeof(flow_label));
-      set_outgoing_flow_label(flow_label);
+      GenerateNewOutgoingFlowLabel();
       expect_peer_flow_label_change_ = true;
+      QUIC_CODE_COUNT(quic_generated_new_flow_label_on_pto);
     }
   }
   if (default_enable_5rto_blackhole_detection_ &&
diff --git a/quiche/quic/core/quic_connection.h b/quiche/quic/core/quic_connection.h
index be9bcb6..693873b 100644
--- a/quiche/quic/core/quic_connection.h
+++ b/quiche/quic/core/quic_connection.h
@@ -1449,7 +1449,9 @@
   }
 
   void EnableBlackholeAvoidanceViaFlowLabel() {
+    GenerateNewOutgoingFlowLabel();
     enable_black_hole_avoidance_via_flow_label_ = true;
+    QUIC_CODE_COUNT(quic_black_hole_avoidance_via_flow_label_enabled);
   }
 
   bool enable_black_hole_avoidance_via_flow_label() const {
@@ -2149,6 +2151,8 @@
 
   bool PeerAddressChanged() const;
 
+  void GenerateNewOutgoingFlowLabel();
+
   QuicAlarm& ack_alarm() { return alarms_.ack_alarm(); }
   const QuicAlarm& ack_alarm() const { return alarms_.ack_alarm(); }
   QuicAlarm& retransmission_alarm() { return alarms_.retransmission_alarm(); }
diff --git a/quiche/quic/core/quic_connection_test.cc b/quiche/quic/core/quic_connection_test.cc
index 8d36e98..6aa7ef3 100644
--- a/quiche/quic/core/quic_connection_test.cc
+++ b/quiche/quic/core/quic_connection_test.cc
@@ -9996,8 +9996,11 @@
   EXPECT_CALL(*send_algorithm_, SetFromConfig(_, _));
   connection_.SetFromConfig(config);
   EXPECT_FALSE(connection_.GetRetransmissionAlarm()->IsSet());
-  connection_.set_outgoing_flow_label(1);
+  EXPECT_EQ(0, connection_.outgoing_flow_label());
   connection_.EnableBlackholeAvoidanceViaFlowLabel();
+  static_cast<test::MockRandom*>(helper_->GetRandomGenerator())->ChangeValue();
+  const uint32_t flow_label = connection_.outgoing_flow_label();
+  EXPECT_NE(0, flow_label);
 
   QuicStreamId stream_id = 2;
   QuicPacketNumber last_packet;
@@ -10009,7 +10012,7 @@
   // Fire PTO and verify the flow label has changed.
   EXPECT_CALL(*send_algorithm_, OnPacketSent(_, _, _, _, _)).Times(1);
   connection_.GetRetransmissionAlarm()->Fire();
-  EXPECT_NE(1, connection_.outgoing_flow_label());
+  EXPECT_NE(flow_label, connection_.outgoing_flow_label());
 }
 
 TEST_P(QuicConnectionTest, NewReceiveNewFlowLabelWithGapChangesFlowLabel) {
@@ -10020,21 +10023,24 @@
   config.SetConnectionOptionsToSend(connection_options);
   EXPECT_CALL(*send_algorithm_, SetFromConfig(_, _));
   connection_.SetFromConfig(config);
+  EXPECT_EQ(0, connection_.outgoing_flow_label());
   connection_.EnableBlackholeAvoidanceViaFlowLabel();
-  const uint32_t flow_label = 1;
-  connection_.set_outgoing_flow_label(flow_label);
+  static_cast<test::MockRandom*>(helper_->GetRandomGenerator())->ChangeValue();
+  const uint32_t flow_label = connection_.outgoing_flow_label();
+  EXPECT_NE(0, flow_label);
   EXPECT_CALL(visitor_, OnStreamFrame(_)).Times(AnyNumber());
 
   // Receive the first packet to initialize the flow label.
   ProcessDataPacketAtLevel(1, !kHasStopWaiting, ENCRYPTION_INITIAL, 0);
-  EXPECT_EQ(1, connection_.outgoing_flow_label());
+  EXPECT_EQ(flow_label, connection_.outgoing_flow_label());
 
   // Receive the second packet with the same flow label
   ProcessDataPacketAtLevel(2, !kHasStopWaiting, ENCRYPTION_INITIAL, flow_label);
-  EXPECT_EQ(1, connection_.outgoing_flow_label());
+  EXPECT_EQ(flow_label, connection_.outgoing_flow_label());
 
   // Receive a packet with gap and a new flow label and verify the outgoing
   // flow label has changed.
+  static_cast<test::MockRandom*>(helper_->GetRandomGenerator())->ChangeValue();
   ProcessDataPacketAtLevel(4, !kHasStopWaiting, ENCRYPTION_INITIAL,
                            flow_label + 1);
   EXPECT_NE(flow_label, connection_.outgoing_flow_label());
@@ -10049,18 +10055,20 @@
   config.SetConnectionOptionsToSend(connection_options);
   EXPECT_CALL(*send_algorithm_, SetFromConfig(_, _));
   connection_.SetFromConfig(config);
+  EXPECT_EQ(0, connection_.outgoing_flow_label());
   connection_.EnableBlackholeAvoidanceViaFlowLabel();
-  const uint32_t flow_label = 1;
-  connection_.set_outgoing_flow_label(flow_label);
+  static_cast<test::MockRandom*>(helper_->GetRandomGenerator())->ChangeValue();
+  const uint32_t flow_label = connection_.outgoing_flow_label();
+  EXPECT_NE(0, flow_label);
   EXPECT_CALL(visitor_, OnStreamFrame(_)).Times(AnyNumber());
 
   // Receive the first packet to initialize the flow label.
   ProcessDataPacketAtLevel(1, !kHasStopWaiting, ENCRYPTION_INITIAL, 0);
-  EXPECT_EQ(1, connection_.outgoing_flow_label());
+  EXPECT_EQ(flow_label, connection_.outgoing_flow_label());
 
   // Receive the second packet with the same flow label
   ProcessDataPacketAtLevel(2, !kHasStopWaiting, ENCRYPTION_INITIAL, flow_label);
-  EXPECT_EQ(1, connection_.outgoing_flow_label());
+  EXPECT_EQ(flow_label, connection_.outgoing_flow_label());
 
   // Receive a packet with no gap and a new flow label and verify the outgoing
   // flow label has not changed.