diff --git a/gdb/gdbthread.h b/gdb/gdbthread.h
index 73f6895fe46..2d6b212cd32 100644
--- a/gdb/gdbthread.h
+++ b/gdb/gdbthread.h
@@ -176,6 +176,9 @@ struct thread_control_state
 
   /* True if the thread is evaluating a BP condition.  */
   bool in_cond_eval = false;
+
+  /* Whether the thread was replaying when the command was issued.  */
+  bool is_replaying = false;
 };
 
 /* Inferior thread specific part of `struct infcall_suspend_state'.  */
diff --git a/gdb/infrun.c b/gdb/infrun.c
index a5030b16376..05022b0d7bc 100644
--- a/gdb/infrun.c
+++ b/gdb/infrun.c
@@ -3096,6 +3096,8 @@ clear_proceed_status_thread (struct thread_info *tp)
 
   /* Discard any remaining commands or status from previous stop.  */
   bpstat_clear (&tp->control.stop_bpstat);
+
+  tp->control.is_replaying = target_record_is_replaying (tp->ptid);
 }
 
 /* Notify the current interpreter and observers that the target is about to
@@ -9009,6 +9011,29 @@ keep_going_pass_signal (struct execution_control_state *ecs)
   gdb_assert (ecs->event_thread->ptid == inferior_ptid);
   gdb_assert (!ecs->event_thread->resumed ());
 
+  /* When a thread reaches the end of its execution history, it automatically
+     stops replaying.  This is so the user doesn't need to explicitly stop it
+     with a separate command.
+
+     We do not want a single command (e.g. continue) to transition from
+     replaying to recording, though, e.g. when starting from a breakpoint we
+     needed to step over at the end of the trace.  When we reach the end of the
+     execution history during stepping, stop with no-history.
+
+     The other direction is fine.  When we're at the end of the execution
+     history, we may reverse-continue to start replaying.  */
+  if (ecs->event_thread->control.is_replaying
+      && !target_record_is_replaying (ecs->event_thread->ptid))
+    {
+      interps_notify_no_history ();
+      ecs->ws.set_no_history ();
+      set_last_target_status (ecs->target, ecs->ptid, ecs->ws);
+      stop_print_frame = true;
+      stop_waiting (ecs);
+      normal_stop ();
+      return;
+    }
+
   /* Save the pc before execution, to compare with pc after stop.  */
   ecs->event_thread->prev_pc
     = regcache_read_pc_protected (get_thread_regcache (ecs->event_thread));
diff --git a/gdb/record-btrace.c b/gdb/record-btrace.c
index 0ef1dfbe652..c1bd2b4bc20 100644
--- a/gdb/record-btrace.c
+++ b/gdb/record-btrace.c
@@ -2339,6 +2339,16 @@ record_btrace_single_step_forward (struct thread_info *tp)
   if (replay == NULL)
     return btrace_step_no_history ();
 
+  /* The execution trace contains (and ends with) the current instruction.
+     This instruction has not been executed, yet, so the trace really ends
+     one instruction earlier.
+
+     We'd fail later on in btrace_insn_next () but we must not trigger
+     breakpoints as we're not really able to step.  */
+  btrace_insn_end (&end, btinfo);
+  if (btrace_insn_cmp (replay, &end) == 0)
+    return btrace_step_no_history ();
+
   /* Check if we're stepping a breakpoint.  */
   if (record_btrace_replay_at_breakpoint (tp))
     return btrace_step_stopped ();
@@ -2361,15 +2371,6 @@ record_btrace_single_step_forward (struct thread_info *tp)
     }
   while (btrace_insn_get (replay) == NULL);
 
-  /* Determine the end of the instruction trace.  */
-  btrace_insn_end (&end, btinfo);
-
-  /* The execution trace contains (and ends with) the current instruction.
-     This instruction has not been executed, yet, so the trace really ends
-     one instruction earlier.  */
-  if (btrace_insn_cmp (replay, &end) == 0)
-    return btrace_step_no_history ();
-
   return btrace_step_spurious ();
 }
 
diff --git a/gdb/testsuite/gdb.btrace/cont-hang.exp b/gdb/testsuite/gdb.btrace/cont-hang.exp
new file mode 100644
index 00000000000..cddcf68b3ab
--- /dev/null
+++ b/gdb/testsuite/gdb.btrace/cont-hang.exp
@@ -0,0 +1,43 @@
+# This testcase is part of GDB, the GNU debugger.
+#
+# Copyright 2024 Free Software Foundation, Inc.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Test that we do not hang when trying to continue over a breakpoint at
+# the end of the trace.
+
+require allow_btrace_tests
+
+standard_testfile record_goto.c
+if [prepare_for_testing "failed to prepare" $testfile $srcfile] {
+    return -1
+}
+
+if ![runto_main] {
+    return -1
+}
+
+# Trace the call to the test function.
+gdb_test_no_output "record btrace"
+gdb_test "next" "main\.3.*"
+
+# We need to be replaying, otherwise, we'd just continue recording.
+gdb_test "reverse-stepi"
+gdb_test "break"
+
+# Continuing will step over the breakpoint and then run into the end of
+# the execution history.  This ends replay, so we can continue recording.
+gdb_test "continue" "No more reverse-execution history.*"
+gdb_continue_to_end
diff --git a/gdb/testsuite/gdb.btrace/step-hang.exp b/gdb/testsuite/gdb.btrace/step-hang.exp
new file mode 100644
index 00000000000..91ea813955d
--- /dev/null
+++ b/gdb/testsuite/gdb.btrace/step-hang.exp
@@ -0,0 +1,42 @@
+# This testcase is part of GDB, the GNU debugger.
+#
+# Copyright 2024 Free Software Foundation, Inc.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Test that we do not hang when trying to step over a breakpoint at the
+# end of the trace.
+
+require allow_btrace_tests
+
+standard_testfile record_goto.c
+if [prepare_for_testing "failed to prepare" $testfile $srcfile] {
+    return -1
+}
+
+if ![runto_main] {
+    return -1
+}
+
+# Trace the call to the test function.
+gdb_test_no_output "record btrace"
+gdb_test "next" "main\.3.*"
+
+# We need to be replaying, otherwise, we'd just continue recording.
+gdb_test "reverse-stepi"
+gdb_test "break"
+
+# Stepping over the breakpoint ends replaying and we can continue recording.
+gdb_test "step"  "main\.3.*"
+gdb_continue_to_end
diff --git a/gdb/testsuite/gdb.btrace/stepn.exp b/gdb/testsuite/gdb.btrace/stepn.exp
new file mode 100644
index 00000000000..4aec90adc65
--- /dev/null
+++ b/gdb/testsuite/gdb.btrace/stepn.exp
@@ -0,0 +1,50 @@
+# This testcase is part of GDB, the GNU debugger.
+#
+# Copyright 2024 Free Software Foundation, Inc.
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Test that step n does not start recording when issued while replaying.
+
+require allow_btrace_tests
+
+standard_testfile record_goto.c
+if [prepare_for_testing "failed to prepare" $testfile $srcfile] {
+    return -1
+}
+
+if ![runto_main] {
+    return -1
+}
+
+# Trace the call to the test function.
+gdb_test_no_output "record btrace"
+gdb_test "next" "main\.3.*"
+
+# Stepping should bring us to the end of the execution history, but should
+# not resume recording.
+with_test_prefix "stepi" {
+    gdb_test "reverse-stepi"
+    gdb_test "stepi 5" "No more reverse-execution history.*main\.3.*"
+}
+
+with_test_prefix "step" {
+    gdb_test "reverse-step"
+    gdb_test "step 5" "No more reverse-execution history.*main\.3.*"
+}
+
+with_test_prefix "next" {
+    gdb_test "reverse-next"
+    gdb_test "next 5" "No more reverse-execution history.*main\.3.*"
+}
