diff --git a/src/lib_scoru_wasm/host_funcs.ml b/src/lib_scoru_wasm/host_funcs.ml
index b3a021de8050a9f98418e336c0ffef76e1e67725..967372a46ec69b3cb310c3d5968ca4578ee2d81f 100644
--- a/src/lib_scoru_wasm/host_funcs.ml
+++ b/src/lib_scoru_wasm/host_funcs.ml
@@ -300,7 +300,7 @@ module Aux = struct
             let* () =
               M.store_num memory id_offset 0l (I64 (Z.to_int64 message_counter))
             in
-            Output_buffer.set_level output_buffer raw_level ;
+            Output_buffer.ensure_outbox_at_level output_buffer raw_level ;
             return (Int32.of_int input_size))
           (fun exn ->
             match exn with
@@ -317,8 +317,8 @@ module Aux = struct
         else
           let num_bytes = Int32.to_int num_bytes in
           let* payload = M.load_bytes memory src num_bytes in
-          let*! () =
-            Output_buffer.set_value output_buffer (Bytes.of_string payload)
+          let*! Output_buffer.{outbox_level = _; message_index = _} =
+            Output_buffer.push_message output_buffer (Bytes.of_string payload)
           in
           return 0l
       in
diff --git a/src/lib_scoru_wasm/test/helpers/ast_generators.ml b/src/lib_scoru_wasm/test/helpers/ast_generators.ml
index 5dfba33251279ce99a77c7ca307d39f5d967d249..af91a202823fb706d1a4ab046f78bf73fafbe603 100644
--- a/src/lib_scoru_wasm/test/helpers/ast_generators.ml
+++ b/src/lib_scoru_wasm/test/helpers/ast_generators.ml
@@ -645,17 +645,17 @@ let output_info_gen =
 
 let output_buffer_gen =
   let* l = list_size (int_range 0 10) int in
-  let s =
+  let outboxes =
     List.map
       (fun _ ->
         generate1
         @@ map
              (fun a ->
-               Output_buffer.Index_Vector.(of_immutable @@ Vector.of_list a))
+               Output_buffer.Messages.(of_immutable @@ Vector.of_list a))
              (list (map Bytes.of_string string)))
       l
   in
-  return Output_buffer.Level_Vector.(of_immutable @@ Vector.of_list s)
+  return Output_buffer.Outboxes.(of_immutable @@ Vector.of_list outboxes)
 
 let label_gen ~module_reg =
   let* label_arity = option (Int32.of_int <$> small_nat) in
diff --git a/src/lib_scoru_wasm/test/helpers/ast_printer.ml b/src/lib_scoru_wasm/test/helpers/ast_printer.ml
index 2ae7aef80a3db292dc17eeb9907ebb556364ad4e..e7b5a13bcde509b7f15c44c09585f53436983d7e 100644
--- a/src/lib_scoru_wasm/test/helpers/ast_printer.ml
+++ b/src/lib_scoru_wasm/test/helpers/ast_printer.ml
@@ -627,19 +627,19 @@ let pp_input_buffer out input =
     (pp_vector_z Input_buffer.pp_message)
     (Lazy_vector.Mutable.ZVector.snapshot input)
 
-let pp_index_vector out index_vector =
+let pp_messages out index_vector =
   Format.fprintf
     out
     "@[<v 2>%a@]"
     (pp_vector_z (fun o x -> Format.fprintf o "@[<v 2>%s@]" (Bytes.to_string x)))
-    (Output_buffer.Index_Vector.snapshot index_vector)
+    (Output_buffer.Messages.snapshot index_vector)
 
 let pp_output_buffer out (output : Output_buffer.t) =
   Format.fprintf
     out
     "@[<v 2>%a@]"
-    (pp_vector (fun o -> pp_index_vector o))
-    (Output_buffer.Level_Vector.snapshot output)
+    (pp_vector (fun o -> pp_messages o))
+    (Output_buffer.Outboxes.snapshot output)
 
 let pp_buffers out Eval.{input; output} =
   Format.fprintf
diff --git a/src/lib_scoru_wasm/test/test_get_set.ml b/src/lib_scoru_wasm/test/test_get_set.ml
index ac3c37af4de22e25f26e7438659366a60a115668..a6a3db6f170fb840e4c828a10857c8fefe79ef7f 100644
--- a/src/lib_scoru_wasm/test/test_get_set.ml
+++ b/src/lib_scoru_wasm/test/test_get_set.ml
@@ -195,8 +195,11 @@ let test_get_output () =
   let* tree = initialise_tree () in
   let* tree = add_input_info tree ~inbox_level:5 ~message_counter:10 in
   let output = Output_buffer.alloc () in
-  Output_buffer.set_level output 0l ;
-  let* () = Output_buffer.set_value output @@ Bytes.of_string "hello" in
+  Output_buffer.ensure_outbox_at_level output 0l ;
+  let* Output_buffer.{outbox_level; message_index} =
+    Output_buffer.push_message output @@ Bytes.of_string "hello"
+  in
+  assert (outbox_level = 0l && Z.equal message_index Z.zero) ;
   let buffers = Eval.{input = Input_buffer.alloc (); output} in
   let* tree =
     Tree_encoding_runner.encode
diff --git a/src/lib_scoru_wasm/test/test_input.ml b/src/lib_scoru_wasm/test/test_input.ml
index 3139945d61a241fdec0671c40313e3659adc66d6..8c8db3d639f52f9d3a378a10ab5415b08f8ad29b 100644
--- a/src/lib_scoru_wasm/test/test_input.ml
+++ b/src/lib_scoru_wasm/test/test_input.ml
@@ -101,9 +101,17 @@ let read_input () =
       ~dst:50l
       ~max_bytes:36000l
   in
-  let* output_level, output_id = Output_buffer.get_id output_buffer in
-  assert (output_level = 2l) ;
-  assert (output_id = Z.of_int (-1)) ;
+  let last_outbox_level = Output_buffer.get_last_level output_buffer in
+  let* last_outbox =
+    match last_outbox_level with
+    | Some level -> Output_buffer.Outboxes.get level output_buffer
+    | None -> Stdlib.failwith "No outbox exists"
+  in
+  let last_message_in_last_outbox =
+    Output_buffer.get_outbox_last_message_index last_outbox
+  in
+  assert (last_outbox_level = Some 2l) ;
+  assert (last_message_in_last_outbox = None) ;
   assert (Input_buffer.num_elements input_buffer = Z.zero) ;
   assert (result = 5l) ;
   let* m = Memory.load_bytes memory 4l 1 in
diff --git a/src/lib_scoru_wasm/test/test_output.ml b/src/lib_scoru_wasm/test/test_output.ml
index b592f6ee78795958c8a8290f2df4374af9ba4c4c..4f592199797de2f9f42aa54cf0ad6271d26a23b6 100644
--- a/src/lib_scoru_wasm/test/test_output.ml
+++ b/src/lib_scoru_wasm/test/test_output.ml
@@ -62,19 +62,33 @@ let test_aux_write_output () =
       ~dst:50l
       ~max_bytes:36000l
   in
-  let output_level = Output_buffer.get_level output_buffer in
-  assert (output_level = 2l) ;
+  let output_level = Output_buffer.get_last_level output_buffer in
+  assert (output_level = Some 2l) ;
   let* result =
     Host_funcs.Aux.write_output ~output_buffer ~memory ~src:50l ~num_bytes:5l
   in
-  let* z = Output_buffer.get output_buffer 2l Z.zero in
+
+  let last_outbox_level = Output_buffer.get_last_level output_buffer in
+  let* last_outbox =
+    match last_outbox_level with
+    | Some level -> Output_buffer.Outboxes.get level output_buffer
+    | None -> Stdlib.failwith "No outbox exists"
+  in
+  let last_message_in_last_outbox =
+    Output_buffer.get_outbox_last_message_index last_outbox
+  in
+  assert (last_outbox_level = Some 2l) ;
+  assert (last_message_in_last_outbox = Some Z.zero) ;
+
+  let* z =
+    Output_buffer.get_message
+      output_buffer
+      {outbox_level = 2l; message_index = Z.zero}
+  in
   assert (result = 0l) ;
-  let* level, id = Output_buffer.get_id output_buffer in
-  assert (level = output_level) ;
-  assert (id = Z.zero) ;
   assert (z = Bytes.of_string "hello") ;
 
-  Lwt.return @@ Result.return_unit
+  Lwt.return_ok ()
 
 let test_write_host_fun () =
   let open Lwt.Syntax in
@@ -126,12 +140,24 @@ let test_write_host_fun () =
       Host_funcs.Internal_for_tests.write_output
       values
   in
-  let* z = Output_buffer.get output 2l Z.zero in
-  let* level, id = Output_buffer.get_id output in
+  let last_outbox_level = Output_buffer.get_last_level output in
+  let* last_outbox =
+    match last_outbox_level with
+    | Some level -> Output_buffer.Outboxes.get level output
+    | None -> Stdlib.failwith "No outbox exists"
+  in
+  let last_message_in_last_outbox =
+    Output_buffer.get_outbox_last_message_index last_outbox
+  in
+  assert (last_outbox_level = Some 2l) ;
+  assert (last_message_in_last_outbox = Some Z.zero) ;
+
+  let* z =
+    Output_buffer.get_message output {outbox_level = 2l; message_index = Z.zero}
+  in
   assert (result = Values.[Num (I32 0l)]) ;
   assert (z = Bytes.of_string "hello") ;
-  assert (level = 2l) ;
-  assert (id = Z.zero) ;
+
   let values = Values.[Num (I32 50l); Num (I32 5000l)] in
   let* _, result =
     Eval.invoke
@@ -143,11 +169,20 @@ let test_write_host_fun () =
       Host_funcs.Internal_for_tests.write_output
       values
   in
-  let* level, id = Output_buffer.get_id output in
+  let last_outbox_level = Output_buffer.get_last_level output in
+  let* last_outbox =
+    match last_outbox_level with
+    | Some level -> Output_buffer.Outboxes.get level output
+    | None ->
+        Stdlib.failwith "The PVM output buffer does not contain any outbox."
+  in
+  let last_message_in_last_outbox =
+    Output_buffer.get_outbox_last_message_index last_outbox
+  in
   assert (
     result = Values.[Num (I32 Host_funcs.Error.(code Input_output_too_large))]) ;
-  assert (level = 2l) ;
-  assert (id = Z.zero) ;
+  assert (last_outbox_level = Some 2l) ;
+  assert (last_message_in_last_outbox = Some Z.zero) ;
   Lwt.return @@ Result.return_unit
 
 let tests =
diff --git a/src/lib_scoru_wasm/wasm_encoding.ml b/src/lib_scoru_wasm/wasm_encoding.ml
index 3f47ec2419d9bb291bb2560d729c39c897a5a741..f03ed383edb952f9cc61cc6d9a8447e45b4c286e 100644
--- a/src/lib_scoru_wasm/wasm_encoding.ml
+++ b/src/lib_scoru_wasm/wasm_encoding.ml
@@ -1206,17 +1206,17 @@ let step_kont_encoding =
         (fun msg -> SK_Trapped Source.(msg @@ no_region));
     ]
 
-let index_vector_encoding =
+let messages_encoding =
   conv
-    (fun index -> Output_buffer.Index_Vector.of_immutable index)
-    (fun buffer -> Output_buffer.Index_Vector.snapshot buffer)
+    (fun index -> Output_buffer.Messages.of_immutable index)
+    (fun buffer -> Output_buffer.Messages.snapshot buffer)
     (z_lazy_vector (value [] Data_encoding.z) (value [] Data_encoding.bytes))
 
 let output_buffer_encoding =
   conv
-    (fun output -> Output_buffer.Level_Vector.of_immutable output)
-    (fun buffer -> Output_buffer.Level_Vector.snapshot buffer)
-    (int32_lazy_vector (value [] Data_encoding.int32) index_vector_encoding)
+    (fun output -> Output_buffer.Outboxes.of_immutable output)
+    (fun buffer -> Output_buffer.Outboxes.snapshot buffer)
+    (int32_lazy_vector (value [] Data_encoding.int32) messages_encoding)
 
 let config_encoding ~host_funcs =
   conv
diff --git a/src/lib_scoru_wasm/wasm_vm.ml b/src/lib_scoru_wasm/wasm_vm.ml
index 15d352a2e942406c133d6e60ef4d5ad33175b67a..9d36ff068eb67d9b2a14cca2a0ef48a6ebff0052 100644
--- a/src/lib_scoru_wasm/wasm_vm.ml
+++ b/src/lib_scoru_wasm/wasm_vm.ml
@@ -500,7 +500,11 @@ let get_output output_info output =
   let open Wasm_pvm_state in
   let {outbox_level; message_index} = output_info in
   let outbox_level = Bounded.Non_negative_int32.to_value outbox_level in
-  let+ payload = Wasm.Output_buffer.get output outbox_level message_index in
+  let+ payload =
+    Wasm.Output_buffer.get_message
+      output
+      Wasm.Output_buffer.{outbox_level; message_index}
+  in
   Bytes.to_string payload
 
 let get_info ({current_tick; last_input_info; _} as pvm_state) =
diff --git a/src/lib_webassembly/runtime/output_buffer.ml b/src/lib_webassembly/runtime/output_buffer.ml
index 67fd2d3e7d1da302f8242335962ed62c0f79e689..6277137be4225d4d9262413c1e097e2d3420bb15 100644
--- a/src/lib_webassembly/runtime/output_buffer.ml
+++ b/src/lib_webassembly/runtime/output_buffer.ml
@@ -3,57 +3,108 @@ type output_info = {
   message_index : Z.t;  (** The index of the message in the outbox. *)
 }
 
-exception Id_too_large
-
-exception Empty_output
+exception Full_outbox
 
 exception Invalid_level
 
 exception Invalid_id
 
-module Index_Vector = Lazy_vector.Mutable.ZVector
-module Level_Vector = Lazy_vector.Mutable.Int32Vector
+module Messages = Lazy_vector.Mutable.ZVector
+module Outboxes = Lazy_vector.Mutable.Int32Vector
 
-type t = bytes Index_Vector.t Level_Vector.t
+type t = bytes Messages.t Outboxes.t
 
-let get_level output = Int32.pred (Level_Vector.num_elements output)
+let get_last_level outboxes =
+  let last_level = Int32.pred (Outboxes.num_elements outboxes) in
+  if last_level < 0l then None else Some last_level
 
-let get_id output =
-  let open Lwt.Syntax in
-  let level = get_level output in
-  if level = -1l then raise Empty_output
+let get_outbox_last_message_index messages =
+  let last_message_index = Z.pred (Messages.num_elements messages) in
+  if Z.Compare.(last_message_index < Z.zero) then None
+  else Some last_message_index
+
+(** Predicates on the outboxes *)
+
+let is_outbox_full outbox =
+  match get_outbox_last_message_index outbox with
+  | Some last_message_index ->
+      Z.Compare.(last_message_index = Z.of_int32 Int32.max_int)
+  | None -> false
+
+let is_outbox_available outboxes level =
+  match get_last_level outboxes with
+  | None -> false
+  | Some last_level -> level <= last_level && level >= 0l
+
+let is_message_available messages index =
+  match get_outbox_last_message_index messages with
+  | None -> false
+  | Some last_message -> Z.Compare.(index <= last_message && index >= Z.zero)
+
+(** Outboxes creation and manipulation *)
+
+(** [alloc ()] allocates a new output_buffer. *)
+let alloc () = Outboxes.create 0l
+
+(** [ensure_outbox_at_level outboxes level] checks the outbox exists for the
+    desired level, and allocates it if it doesn't (and also allocates the
+    previous outboxes if they don't exists).
+
+    @raise Invalid_level if the level is negative.
+*)
+let ensure_outbox_at_level outboxes level =
+  if level < 0l then raise Invalid_level
   else
-    let* last = Level_Vector.(get level output) in
-    Lwt.return @@ (level, Z.pred (Index_Vector.num_elements last))
+    let diff =
+      match get_last_level outboxes with
+      | None ->
+          (* No outbox exists yet, we need to create `level + 1` inboxes
+             (level `0` and the rest). *)
+          Int32.succ level
+      | Some curr_level ->
+          (* If the desired outbox is below the current maximum, we ensure won't
+             grow the vector with a negative diff. *)
+          Int32.(max (sub level curr_level) 0l)
+    in
+    Outboxes.grow ~default:(fun () -> Messages.create Z.zero) diff outboxes
 
-let set_level output level =
-  Level_Vector.grow
-    ~default:(fun () -> Index_Vector.create Z.zero)
-    (Int32.sub level (get_level output))
-    output
+(** [singleton_outbox msg] creates a new outbox with a unique message. *)
+let singleton_outbox msg =
+  let outbox = Messages.create Z.zero in
+  Messages.cons msg outbox ;
+  outbox
 
-let index_create a =
-  let init = Index_Vector.create Z.zero in
-  Index_Vector.cons a init ;
-  init
+(** [push_message outboxes msg] push a new message in the last outbox, and
+    returns the its level and index in the outbox.
 
-let set_value output a =
+    @raise Full_outbox if the last outbox is full.
+*)
+let push_message outboxes msg =
   let open Lwt.Syntax in
-  let* level, index = get_id output in
-  if level = -1l then Lwt.return @@ Level_Vector.cons (index_create a) output
-  else if Z.to_int32 index >= Int32.max_int then raise Id_too_large
-  else
-    let* last = Level_Vector.get level output in
-    Lwt.return @@ Index_Vector.grow ~default:(fun () -> a) Z.one last
+  let last_level = get_last_level outboxes in
+  match last_level with
+  | None ->
+      (* There's no outbox at all, we push a new singleton one. *)
+      Outboxes.cons (singleton_outbox msg) outboxes ;
+      Lwt.return {outbox_level = 0l; message_index = Z.zero}
+  | Some outbox_level ->
+      (* The outbox exists, we check it can contain more messages and append the
+         new message. *)
+      let+ last_outbox = Outboxes.get outbox_level outboxes in
+      if is_outbox_full last_outbox then raise Full_outbox
+      else
+        let new_message_index = Messages.append msg last_outbox in
+        {outbox_level; message_index = new_message_index}
 
-let get output level index =
-  let max_level = get_level output in
-  if level > max_level || level < 0l then raise Invalid_level
-  else
-    let open Lwt.Syntax in
-    let* index_vector = Level_Vector.get level output in
-    let max_index = Z.pred @@ Index_Vector.num_elements index_vector in
-    if index > max_index || index < Z.zero then raise Invalid_id
-    else Index_Vector.get index index_vector
+(** [get_message outboxes message_info] finds a message in the output buffer.
 
-let alloc () = Level_Vector.create 0l
+    @raise Invalid_level if no outbox exists for the given level.
+    @raise Invalid_id if no message with the given id exists in the outbox at
+      this level.*)
+let get_message outboxes {outbox_level; message_index} =
+  let open Lwt.Syntax in
+  if not (is_outbox_available outboxes outbox_level) then raise Invalid_level
+  else
+    let* outbox = Outboxes.get outbox_level outboxes in
+    if not (is_message_available outbox message_index) then raise Invalid_id
+    else Messages.get message_index outbox
diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_wasm.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_wasm.ml
index 82a7afc1f409eeb96efb24ceec6982a1e9f0cf65..e01dbeb7999ced3fc4bd90fa2638811fd0ed9d5c 100644
--- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_wasm.ml
+++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_wasm.ml
@@ -255,15 +255,28 @@ let test_output () =
   let*! tree = set_full_input_step [string_input_message] 0l tree in
   let*! final_tree = eval_until_input_requested tree in
   let*! output = Wasm.Internal_for_tests.get_output_buffer final_tree in
-  let*! level, end_of_level_message_index =
-    Tezos_webassembly_interpreter.Output_buffer.get_id output
+  let* last_outbox_level =
+    match Tezos_webassembly_interpreter.Output_buffer.get_last_level output with
+    | Some level -> return level
+    | None -> failwith "The PVM output buffer does not contain any outbox."
+  in
+  let*! last_outbox =
+    Tezos_webassembly_interpreter.Output_buffer.Outboxes.get
+      last_outbox_level
+      output
+  in
+  let* end_of_level_message_index =
+    match Output_buffer.get_outbox_last_message_index last_outbox with
+    | Some index -> return index
+    | None -> failwith "The PVM output buffer does not contain any outbox."
   in
   (* The last message in the outbox corresponds to EOL, due to the nature of the
      kernel. As such we must take the one preceding it. *)
   let message_index = Z.pred end_of_level_message_index in
 
   let*! bytes_output_message =
-    Tezos_webassembly_interpreter.Output_buffer.get output level message_index
+    Tezos_webassembly_interpreter.Output_buffer.(
+      get_message output {outbox_level = last_outbox_level; message_index})
   in
   assert (string_input_message = Bytes.to_string bytes_output_message) ;
   let message =
@@ -273,7 +286,7 @@ let test_output () =
   in
   assert (message = out) ;
   let*? outbox_level =
-    Environment.wrap_tzresult @@ Raw_level_repr.of_int32 level
+    Environment.wrap_tzresult @@ Raw_level_repr.of_int32 last_outbox_level
   in
   let output = Sc_rollup_PVM_sig.{outbox_level; message_index; message} in