diff --git a/core.c b/core.c
index 274cd91..58826bc 100644
--- a/core.c
+++ b/core.c
@@ -30,6 +30,16 @@
 #define MCTP_MAX_BUSSES 2
 #endif
 
+/* Concurrent reassembly contexts. */
+#ifndef MCTP_REASSEMBLY_CTXS
+#define MCTP_REASSEMBLY_CTXS 16
+#endif
+
+/* Outbound request tags */
+#ifndef MCTP_REQ_TAGS
+#define MCTP_REQ_TAGS MCTP_REASSEMBLY_CTXS
+#endif
+
 /* Internal data structures */
 
 enum mctp_bus_state {
@@ -74,6 +84,13 @@
 	size_t fragment_size;
 };
 
+struct mctp_req_tag {
+	/* 0 is an unused entry */
+	mctp_eid_t local;
+	mctp_eid_t remote;
+	uint8_t tag;
+};
+
 struct mctp {
 	int n_busses;
 	struct mctp_bus busses[MCTP_MAX_BUSSES];
@@ -86,10 +103,13 @@
 	mctp_capture_fn capture;
 	void *capture_data;
 
-	/* Message reassembly.
-	 * @todo: flexible context count
-	 */
-	struct mctp_msg_ctx msg_ctxs[16];
+	/* Message reassembly. */
+	struct mctp_msg_ctx msg_ctxs[MCTP_REASSEMBLY_CTXS];
+
+	/* Allocated outbound TO tags */
+	struct mctp_req_tag req_tags[MCTP_REQ_TAGS];
+	/* used to avoid always allocating tag 0 */
+	uint8_t tag_round_robin;
 
 	enum {
 		ROUTE_ENDPOINT,
@@ -107,6 +127,8 @@
 static int mctp_message_tx_on_bus(struct mctp_bus *bus, mctp_eid_t src,
 				  mctp_eid_t dest, bool tag_owner,
 				  uint8_t msg_tag, void *msg, size_t msg_len);
+static void mctp_dealloc_tag(struct mctp_bus *bus, mctp_eid_t local,
+			     mctp_eid_t remote, uint8_t tag);
 
 struct mctp_pktbuf *mctp_pktbuf_alloc(struct mctp_binding *binding, size_t len)
 {
@@ -531,6 +553,11 @@
 
 	if (mctp->route_policy == ROUTE_ENDPOINT &&
 	    mctp_rx_dest_is_local(bus, dest)) {
+		/* Note responses to allocated tags */
+		if (!tag_owner) {
+			mctp_dealloc_tag(bus, dest, src, msg_tag);
+		}
+
 		/* Handle MCTP Control Messages: */
 		if (len >= sizeof(struct mctp_ctrl_msg_hdr)) {
 			struct mctp_ctrl_msg_hdr *msg_hdr = buf;
@@ -961,6 +988,95 @@
 				       msg_len);
 }
 
+static void mctp_dealloc_tag(struct mctp_bus *bus, mctp_eid_t local,
+			     mctp_eid_t remote, uint8_t tag)
+{
+	struct mctp *mctp = bus->binding->mctp;
+	if (local == 0 || remote == 0) {
+		return;
+	}
+
+	for (size_t i = 0; i < ARRAY_SIZE(mctp->req_tags); i++) {
+		struct mctp_req_tag *r = &mctp->req_tags[i];
+		if (r->local == local && r->remote == remote && r->tag == tag) {
+			r->local = 0;
+			r->remote = 0;
+			r->tag = 0;
+			return;
+		}
+	}
+}
+
+static int mctp_alloc_tag(struct mctp *mctp, mctp_eid_t local,
+			  mctp_eid_t remote, uint8_t *ret_tag)
+{
+	assert(local != 0);
+	assert(remote != 0);
+
+	uint8_t used = 0;
+	struct mctp_req_tag *spare = NULL;
+	/* Find which tags and slots are used/spare */
+	for (size_t i = 0; i < ARRAY_SIZE(mctp->req_tags); i++) {
+		struct mctp_req_tag *r = &mctp->req_tags[i];
+		if (r->local == 0) {
+			spare = r;
+		} else {
+			// TODO: check timeouts
+			if (r->local == local && r->remote == remote) {
+				used |= 1 << r->tag;
+			}
+		}
+	}
+
+	if (spare == NULL) {
+		// All req_tag slots are in-use
+		return -EBUSY;
+	}
+
+	for (uint8_t t = 0; t < 8; t++) {
+		uint8_t tag = (t + mctp->tag_round_robin) % 8;
+		if ((used & 1 << tag) == 0) {
+			spare->local = local;
+			spare->remote = remote;
+			spare->tag = tag;
+			*ret_tag = tag;
+			mctp->tag_round_robin = (tag + 1) % 8;
+			return 0;
+		}
+	}
+
+	// All 8 tags are used for this src/dest pair
+	return -EBUSY;
+}
+
+int mctp_message_tx_request(struct mctp *mctp, mctp_eid_t eid, void *msg,
+			    size_t msg_len, uint8_t *ret_alloc_msg_tag)
+{
+	int rc;
+	struct mctp_bus *bus;
+
+	bus = find_bus_for_eid(mctp, eid);
+	if (!bus) {
+		__mctp_msg_free(msg, mctp);
+		return 0;
+	}
+
+	uint8_t alloc_tag;
+	rc = mctp_alloc_tag(mctp, bus->eid, eid, &alloc_tag);
+	if (rc) {
+		mctp_prdebug("Failed allocating tag");
+		__mctp_msg_free(msg, mctp);
+		return rc;
+	}
+
+	if (ret_alloc_msg_tag) {
+		*ret_alloc_msg_tag = alloc_tag;
+	}
+
+	return mctp_message_tx_alloced(mctp, eid, true, alloc_tag, msg,
+				       msg_len);
+}
+
 bool mctp_is_tx_ready(struct mctp *mctp, mctp_eid_t eid)
 {
 	struct mctp_bus *bus;
diff --git a/libmctp.h b/libmctp.h
index 680dc39..a8f952a 100644
--- a/libmctp.h
+++ b/libmctp.h
@@ -150,6 +150,22 @@
 int mctp_message_tx(struct mctp *mctp, mctp_eid_t eid, bool tag_owner,
 		    uint8_t msg_tag, const void *msg, size_t msg_len);
 
+/* Transmit a request message.
+ * @msg: The message buffer to send. Must be suitable for
+ * free(), or the custom mctp_set_alloc_ops() m_msg_free.
+ *
+ * A tag with Tag Owner bit set will allocated for the sent message,
+ * and returned to the caller (TO bit is unset in the returned @alloc_msg_tag).
+ * alloc_msg_tag may be NULL to ignore the returned tag.
+ * If no tags are spare -EBUSY will be returned.
+ *
+ * If an asynchronous binding is being used, it will return -EBUSY if
+ * a message is already pending for transmission (msg will be freed).
+ * Asynchronous users can test mctp_is_tx_ready() prior to sending.
+ */
+int mctp_message_tx_request(struct mctp *mctp, mctp_eid_t eid, void *msg,
+			    size_t msg_len, uint8_t *alloc_msg_tag);
+
 bool mctp_is_tx_ready(struct mctp *mctp, mctp_eid_t eid);
 
 /* hardware bindings */
diff --git a/tests/test_core.c b/tests/test_core.c
index 2f5d2c7..9c17100 100644
--- a/tests/test_core.c
+++ b/tests/test_core.c
@@ -1,5 +1,4 @@
 /* SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later */
-
 #define _GNU_SOURCE
 
 #ifdef NDEBUG
@@ -18,6 +17,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <errno.h>
 
 #include "compiler.h"
 #include "libmctp-alloc.h"
@@ -602,6 +602,76 @@
 	mctp_destroy(mctp);
 }
 
+/*
+ * This test case tests tag allocation. 8 tags
+ * are allowed to be pending.
+ */
+static void mctp_core_test_tx_alloc_tag()
+{
+	struct mctp *mctp = NULL;
+	struct mctp_binding_test *binding = NULL;
+	struct test_params test_param;
+	uint8_t msg_tag;
+	void *msg;
+	int rc;
+	mctp_eid_t dest_eid1 = 30;
+	size_t msg_len = 10;
+
+	mctp_test_stack_init(&mctp, &binding, dest_eid1);
+	mctp_set_rx_all(mctp, rx_message, &test_param);
+
+	uint8_t used = 0;
+	for (int i = 0; i < 8; i++) {
+		test_param.seen = false;
+		test_param.msg_tag = 0xff;
+		test_param.tag_owner = false;
+
+		msg = __mctp_alloc(msg_len);
+		memset(msg, 0x99, msg_len);
+		rc = mctp_message_tx_request(mctp, dest_eid1, msg, msg_len,
+					     &msg_tag);
+		assert(rc == 0);
+		assert(test_param.seen == true);
+		assert(test_param.msg_tag == msg_tag);
+		assert(test_param.tag_owner == true);
+		used |= (1 << msg_tag);
+	}
+	assert(used == 0xff);
+
+	/* Ran out of tags */
+	test_param.seen = false;
+	msg = __mctp_alloc(msg_len);
+	memset(msg, 0x99, msg_len);
+	rc = mctp_message_tx_request(mctp, dest_eid1, msg, msg_len, &msg_tag);
+	assert(rc == -EBUSY);
+	assert(test_param.seen == false);
+
+	/* Send/Receive a response to one of those tags */
+	test_param.seen = false;
+	msg = __mctp_alloc(msg_len);
+	memset(msg, 0x99, msg_len);
+	/* Arbitrary one */
+	uint8_t replied_tag = 3;
+	rc = mctp_message_tx_alloced(mctp, dest_eid1, false, replied_tag, msg,
+				     msg_len);
+	assert(rc == 0);
+	assert(test_param.seen == true);
+	assert(test_param.msg_tag == replied_tag);
+	assert(test_param.tag_owner == false);
+
+	/* Now sending allocates that tag again, since it is the only spare one */
+	test_param.seen = false;
+	msg = __mctp_alloc(msg_len);
+	memset(msg, 0x99, msg_len);
+	rc = mctp_message_tx_request(mctp, dest_eid1, msg, msg_len, &msg_tag);
+	assert(rc == 0);
+	assert(test_param.seen == true);
+	assert(msg_tag == replied_tag);
+
+	mctp_binding_test_destroy(binding);
+	mctp_destroy(mctp);
+}
+
 /* clang-format off */
 #define TEST_CASE(test) { #test, test }
 static const struct {
@@ -620,6 +690,7 @@
 	TEST_CASE(mctp_core_test_rx_with_tag_multifragment),
 	TEST_CASE(mctp_core_test_rx_with_null_dst_eid),
 	TEST_CASE(mctp_core_test_rx_with_broadcast_dst_eid),
+	TEST_CASE(mctp_core_test_tx_alloc_tag),
 };
 /* clang-format on */