diff --git a/openbsc/include/openbsc/bsc_nat.h b/openbsc/include/openbsc/bsc_nat.h
index 1950318..f93b596 100644
--- a/openbsc/include/openbsc/bsc_nat.h
+++ b/openbsc/include/openbsc/bsc_nat.h
@@ -45,6 +45,7 @@
 struct bsc_nat_parsed;
 struct bsc_nat;
 struct bsc_nat_ussd_con;
+struct nat_rewrite_rule;
 
 enum {
 	NAT_CON_TYPE_NONE,
@@ -308,6 +309,10 @@
 	char *sms_num_rewr_name;
 	struct llist_head sms_num_rewr;
 
+	/* more rewriting */
+	char *num_rewr_trie_name;
+	struct nat_rewrite *num_rewr_trie;
+
 	/* USSD messages  we want to match */
 	char *ussd_lst_name;
 	char *ussd_query;
@@ -452,6 +457,7 @@
 	regex_t num_reg;
 
 	char *replace;
+	uint8_t is_prefix_lookup;
 };
 
 void bsc_nat_num_rewr_entry_adapt(void *ctx, struct llist_head *head, const struct osmo_config_list *);
diff --git a/openbsc/include/openbsc/nat_rewrite_trie.h b/openbsc/include/openbsc/nat_rewrite_trie.h
index 4445c3e..0571099 100644
--- a/openbsc/include/openbsc/nat_rewrite_trie.h
+++ b/openbsc/include/openbsc/nat_rewrite_trie.h
@@ -22,13 +22,15 @@
 
 #include <osmocom/core/linuxrbtree.h>
 
+struct vty;
+
 struct nat_rewrite_rule {
 	/* For digits 0-9 and + */
 	struct nat_rewrite_rule *rules[11];
 
 	char empty;
 	char prefix[14];
-	char rewrite[4];
+	char rewrite[6];
 };
 
 struct nat_rewrite {
@@ -40,5 +42,6 @@
 struct nat_rewrite *nat_rewrite_parse(void *ctx, const char *filename);
 struct nat_rewrite_rule *nat_rewrite_lookup(struct nat_rewrite *, const char *prefix);
 void nat_rewrite_dump(struct nat_rewrite *rewr);
+void nat_rewrite_dump_vty(struct vty *vty, struct nat_rewrite *rewr);
 
 #endif
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c
index 06071c4..5984d96 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c
@@ -27,6 +27,7 @@
 #include <openbsc/gsm_data.h>
 #include <openbsc/debug.h>
 #include <openbsc/ipaccess.h>
+#include <openbsc/nat_rewrite_trie.h>
 
 #include <osmocom/core/linuxlist.h>
 #include <osmocom/core/talloc.h>
@@ -37,9 +38,30 @@
 
 #include <osmocom/sccp/sccp.h>
 
+static char *trie_lookup(struct nat_rewrite *trie, const char *number,
+			regoff_t off, void *ctx)
+{
+	struct nat_rewrite_rule *rule;
+
+	if (!trie) {
+		LOGP(DNAT, LOGL_ERROR,
+			"Asked to do a table lookup but no table.\n");
+		return NULL;
+	}
+
+	rule = nat_rewrite_lookup(trie, number);
+	if (!rule) {
+		LOGP(DNAT, LOGL_DEBUG,
+			"Couldn't find a prefix rule for %s\n", number);
+		return NULL;
+	}
+
+	return talloc_asprintf(ctx, "%s%s", rule->rewrite, &number[off]);
+}
+
 static char *match_and_rewrite_number(void *ctx, const char *number,
-				      const char *imsi,
-				      struct llist_head *list)
+				const char *imsi, struct llist_head *list,
+				struct nat_rewrite *trie)
 {
 	struct bsc_nat_num_rewr_entry *entry;
 	char *new_number = NULL;
@@ -53,11 +75,17 @@
 			continue;
 
 		/* this regexp matches... */
-		if (regexec(&entry->num_reg, number, 2, matches, 0) == 0 &&
-		    matches[1].rm_eo != -1)
-			new_number = talloc_asprintf(ctx, "%s%s",
+		if (regexec(&entry->num_reg, number, 2, matches, 0) == 0
+			&& matches[1].rm_eo != -1) {
+			if (entry->is_prefix_lookup)
+				new_number = trie_lookup(trie, number,
+						matches[1].rm_so, ctx);
+			else
+				new_number = talloc_asprintf(ctx, "%s%s",
 					entry->replace,
 					&number[matches[1].rm_so]);
+		}
+
 		if (new_number)
 			break;
 	}
@@ -86,7 +114,7 @@
 	}
 
 	return match_and_rewrite_number(ctx, number,
-					imsi, &nat->num_rewr);
+					imsi, &nat->num_rewr, nat->num_rewr_trie);
 }
 
 
@@ -261,7 +289,7 @@
 			     const char *imsi, const char *dest_nr)
 {
 	return match_and_rewrite_number(ctx, dest_nr, imsi,
-					&nat->sms_num_rewr);
+					&nat->sms_num_rewr, NULL);
 }
 
 /**
@@ -600,6 +628,9 @@
 			continue;
 		}
 
+		if (strcmp("prefix_lookup", entry->replace) == 0)
+			entry->is_prefix_lookup = 1;
+
 		/* we will now build a regexp string */
 		if (cfg_entry->mcc[0] == '^') {
 			regexp = talloc_strdup(entry, cfg_entry->mcc);
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
index 57043ac..faceb59 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
@@ -21,6 +21,7 @@
 
 #include <openbsc/nat_rewrite_trie.h>
 #include <openbsc/debug.h>
+#include <openbsc/vty.h>
 
 #include <osmocom/core/talloc.h>
 #include <osmocom/core/utils.h>
@@ -238,3 +239,21 @@
 {
 	nat_rewrite_dump_rec(&rewrite->rule);
 }
+
+static void nat_rewrite_dump_rec_vty(struct vty *vty, struct nat_rewrite_rule *rule)
+{
+	int i;
+	if (!rule->empty)
+		vty_out(vty, "%s,%s%s", rule->prefix, rule->rewrite, VTY_NEWLINE);
+
+	for (i = 0; i < ARRAY_SIZE(rule->rules); ++i) {
+		if (!rule->rules[i])
+			continue;
+		nat_rewrite_dump_rec_vty(vty, rule->rules[i]);
+	}
+}
+
+void nat_rewrite_dump_vty(struct vty *vty, struct nat_rewrite *rewrite)
+{
+	nat_rewrite_dump_rec_vty(vty, &rewrite->rule);
+}
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c b/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c
index 6774a42..5404bfb 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c
@@ -26,6 +26,7 @@
 #include <openbsc/gsm_04_08.h>
 #include <openbsc/mgcp.h>
 #include <openbsc/vty.h>
+#include <openbsc/nat_rewrite_trie.h>
 
 #include <osmocom/core/talloc.h>
 #include <osmocom/core/rate_ctr.h>
@@ -138,6 +139,9 @@
 	if (_nat->sms_num_rewr_name)
 		vty_out(vty, " sms-number-rewrite %s%s",
 			_nat->sms_num_rewr_name, VTY_NEWLINE);
+	if (_nat->num_rewr_trie_name)
+		vty_out(vty, " prefix-tree %s%s",
+			_nat->num_rewr_trie_name, VTY_NEWLINE);
 
 	llist_for_each_entry(lst, &_nat->access_lists, list)
 		write_acc_lst(vty, lst);
@@ -633,6 +637,59 @@
 	return CMD_SUCCESS;
 }
 
+DEFUN(cfg_nat_prefix_trie,
+      cfg_nat_prefix_trie_cmd,
+      "prefix-tree FILENAME",
+      "Prefix tree for number rewriting\n" "File to load\n")
+{
+	/* give up the old data */
+	talloc_free(_nat->num_rewr_trie);
+	_nat->num_rewr_trie = NULL;
+
+	/* replace the file name */
+	bsc_replace_string(_nat, &_nat->num_rewr_trie_name, argv[0]);
+	if (!_nat->num_rewr_trie_name) {
+		vty_out(vty, "%% prefix-tree no filename is present.%s", VTY_NEWLINE);
+		return CMD_WARNING;
+	}
+
+	_nat->num_rewr_trie = nat_rewrite_parse(_nat, _nat->num_rewr_trie_name);
+	if (!_nat->num_rewr_trie) {
+		vty_out(vty, "%% prefix-tree parsing has failed.%s", VTY_NEWLINE);
+		return CMD_WARNING;
+	}
+
+	vty_out(vty, "%% prefix-tree loaded %zu rules.%s",
+		_nat->num_rewr_trie->prefixes, VTY_NEWLINE);
+	return CMD_SUCCESS;
+}
+
+DEFUN(cfg_nat_no_prefix_trie, cfg_nat_no_prefix_trie_cmd,
+      "no prefix-tree",
+      NO_STR "Prefix tree for number rewriting\n")
+{
+	talloc_free(_nat->num_rewr_trie);
+	_nat->num_rewr_trie = NULL;
+	talloc_free(_nat->num_rewr_trie_name);
+	_nat->num_rewr_trie_name = NULL;
+
+	return CMD_SUCCESS;
+}
+
+DEFUN(show_prefix_tree, show_prefix_tree_cmd,
+      "show prefix-tree",
+      SHOW_STR "Prefix tree for number rewriting\n")
+{
+	if (!_nat->num_rewr_trie) {
+		vty_out(vty, "%% there is now prefix tree loaded.%s",
+			VTY_NEWLINE);
+		return CMD_WARNING;
+	}
+
+	nat_rewrite_dump_vty(vty, _nat->num_rewr_trie);
+	return CMD_SUCCESS;
+}
+
 DEFUN(cfg_nat_ussd_lst_name,
       cfg_nat_ussd_lst_name_cmd,
       "ussd-list-name NAME",
@@ -1089,6 +1146,7 @@
 	install_element_ve(&show_bsc_mgcp_cmd);
 	install_element_ve(&show_acc_lst_cmd);
 	install_element_ve(&show_bar_lst_cmd);
+	install_element_ve(&show_prefix_tree_cmd);
 
 	install_element(ENABLE_NODE, &set_last_endp_cmd);
 	install_element(ENABLE_NODE, &block_new_conn_cmd);
@@ -1131,6 +1189,8 @@
 	install_element(NAT_NODE, &cfg_nat_no_sms_clear_tpsrr_cmd);
 	install_element(NAT_NODE, &cfg_nat_sms_number_rewrite_cmd);
 	install_element(NAT_NODE, &cfg_nat_no_sms_number_rewrite_cmd);
+	install_element(NAT_NODE, &cfg_nat_prefix_trie_cmd);
+	install_element(NAT_NODE, &cfg_nat_no_prefix_trie_cmd);
 
 	install_element(NAT_NODE, &cfg_nat_pgroup_cmd);
 	install_element(NAT_NODE, &cfg_nat_no_pgroup_cmd);
diff --git a/openbsc/tests/bsc-nat/Makefile.am b/openbsc/tests/bsc-nat/Makefile.am
index 0847678..1078d9b 100644
--- a/openbsc/tests/bsc-nat/Makefile.am
+++ b/openbsc/tests/bsc-nat/Makefile.am
@@ -2,7 +2,7 @@
 AM_CFLAGS=-Wall -ggdb3 $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGSM_CFLAGS) $(LIBOSMOSCCP_CFLAGS) $(LIBOSMOABIS_CFLAGS) $(COVERAGE_CFLAGS)
 AM_LDFLAGS = $(COVERAGE_LDFLAGS)
 
-EXTRA_DIST = bsc_nat_test.ok bsc_data.c barr.cfg barr_dup.cfg
+EXTRA_DIST = bsc_nat_test.ok bsc_data.c barr.cfg barr_dup.cfg prefixes.csv
 
 noinst_PROGRAMS = bsc_nat_test
 
@@ -12,6 +12,7 @@
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_utils.c \
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_filter.c \
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_rewrite.c \
+			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c \
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_mgcp_utils.c
 bsc_nat_test_LDADD = $(top_builddir)/src/libbsc/libbsc.a \
 			$(top_srcdir)/src/libctrl/libctrl.a \
diff --git a/openbsc/tests/bsc-nat/bsc_nat_test.c b/openbsc/tests/bsc-nat/bsc_nat_test.c
index 4a244db..b035004 100644
--- a/openbsc/tests/bsc-nat/bsc_nat_test.c
+++ b/openbsc/tests/bsc-nat/bsc_nat_test.c
@@ -26,6 +26,7 @@
 #include <openbsc/gsm_data.h>
 #include <openbsc/bsc_nat.h>
 #include <openbsc/bsc_nat_sccp.h>
+#include <openbsc/nat_rewrite_trie.h>
 
 #include <osmocom/core/application.h>
 #include <osmocom/core/backtrace.h>
@@ -1041,6 +1042,55 @@
 	msgb_free(out);
 }
 
+static void test_setup_rewrite_prefix(void)
+{
+	struct msgb *msg = msgb_alloc(4096, "test_dt_filter");
+	struct msgb *out;
+	struct bsc_nat_parsed *parsed;
+	const char *imsi = "27408000001234";
+
+	struct bsc_nat *nat = bsc_nat_alloc();
+
+	/* a fake list */
+	struct osmo_config_list entries;
+	struct osmo_config_entry entry;
+
+	INIT_LLIST_HEAD(&entries.entry);
+	entry.mcc = "274";
+	entry.mnc = "08";
+	entry.option = "^0([1-9])";
+	entry.text = "prefix_lookup";
+	llist_add_tail(&entry.list, &entries.entry);
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr, &entries);
+
+        nat->num_rewr_trie = nat_rewrite_parse(nat, "prefixes.csv");
+
+	msgb_reset(msg);
+	copy_to_msg(msg, cc_setup_national, ARRAY_SIZE(cc_setup_national));
+	parsed = bsc_nat_parse(msg);
+	if (!parsed) {
+		printf("FAIL: Could not parse ID resp\n");
+		abort();
+	}
+
+	out = bsc_nat_rewrite_msg(nat, msg, parsed, imsi);
+	if (!out) {
+		printf("FAIL: A new message should be created.\n");
+		abort();
+	}
+
+	if (msg == out) {
+		printf("FAIL: The message should have changed\n");
+		abort();
+	}
+
+	verify_msg(out, cc_setup_national_patched, ARRAY_SIZE(cc_setup_national_patched));
+	msgb_free(out);
+
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr, NULL);
+	talloc_free(nat);
+}
+
 static void test_sms_smsc_rewrite()
 {
 	struct msgb *msg = msgb_alloc(4096, "SMSC rewrite"), *out;
@@ -1322,6 +1372,7 @@
 	test_cr_filter();
 	test_dt_filter();
 	test_setup_rewrite();
+	test_setup_rewrite_prefix();
 	test_sms_smsc_rewrite();
 	test_sms_number_rewrite();
 	test_mgcp_allocations();
diff --git a/openbsc/tests/bsc-nat/prefixes.csv b/openbsc/tests/bsc-nat/prefixes.csv
new file mode 100644
index 0000000..0b66ffe
--- /dev/null
+++ b/openbsc/tests/bsc-nat/prefixes.csv
@@ -0,0 +1 @@
+0172,0049
diff --git a/openbsc/tests/testsuite.at b/openbsc/tests/testsuite.at
index 148b3d3..e54d4b5 100644
--- a/openbsc/tests/testsuite.at
+++ b/openbsc/tests/testsuite.at
@@ -34,6 +34,7 @@
 AT_SETUP([bsc-nat])
 AT_KEYWORDS([bsc-nat])
 AT_CHECK([test "$enable_nat_test" != no || exit 77])
+cp $abs_srcdir/bsc-nat/prefixes.csv .
 cp $abs_srcdir/bsc-nat/barr.cfg .
 cp $abs_srcdir/bsc-nat/barr_dup.cfg .
 cat $abs_srcdir/bsc-nat/bsc_nat_test.ok > expout
diff --git a/openbsc/tests/vty_test_runner.py b/openbsc/tests/vty_test_runner.py
index 456573d..91b4684 100644
--- a/openbsc/tests/vty_test_runner.py
+++ b/openbsc/tests/vty_test_runner.py
@@ -103,6 +103,27 @@
         res = self.vty.command("number-rewrite rewrite.cfg")
         res = self.vty.command("no number-rewrite")
 
+    def testPrefixTreeLoading(self):
+        cfg = os.path.join(confpath, "tests/bsc-nat-trie/prefixes.csv")
+
+        self.vty.enable()
+        self.vty.command("configure terminal")
+        self.vty.command("nat")
+        res = self.vty.command("prefix-tree %s" % cfg)
+        self.assertEqual(res, "% prefix-tree loaded 17 rules.")
+        self.vty.command("end")
+
+        res = self.vty.command("show prefix-tree")
+        self.assertEqual(res, '1,1\r\n12,2\r\n123,3\r\n1234,4\r\n12345,5\r\n123456,6\r\n1234567,7\r\n12345678,8\r\n123456789,9\r\n1234567890,10\r\n13,11\r\n14,12\r\n15,13\r\n16,14\r\n82,16\r\n823455,15\r\n+49123,17')
+
+        self.vty.command("configure terminal")
+        self.vty.command("nat")
+        self.vty.command("no prefix-tree")
+        self.vty.command("end")
+
+        res = self.vty.command("show prefix-tree")
+        self.assertEqual(res, "% there is now prefix tree loaded.")
+
 
 def add_nat_test(suite, workdir):
     if not os.path.isfile(os.path.join(workdir, "src/osmo-bsc_nat/osmo-bsc_nat")):