diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c b/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
index 36a7cfb..96b937c 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
@@ -1071,7 +1071,10 @@
 		msgb_v_put(out, data_ptr[1]);
 
 		/* encode the new number and put it */
-		sms_encode_addr_element(out, new_dest_nr, 0x81, 1);
+		if (strncmp(new_dest_nr, "00", 2) == 0)
+			sms_encode_addr_element(out, new_dest_nr + 2, 0x91, 1);
+		else
+			sms_encode_addr_element(out, new_dest_nr, 0x81, 1);
 
 		/* Copy the rest after the TP-DS */
 		data = msgb_put(out, data_len - 2 - 1 - old_dest_len);
diff --git a/openbsc/tests/bsc-nat/bsc_data.c b/openbsc/tests/bsc-nat/bsc_data.c
index d8a0c87..6a984f6 100644
--- a/openbsc/tests/bsc-nat/bsc_data.c
+++ b/openbsc/tests/bsc-nat/bsc_data.c
@@ -128,11 +128,11 @@
 };
 
 static const uint8_t smsc_rewrite_num_patched[] = {
-0x00, 0x30, 0xfd, 0x06, 0x01, 0x13, 0x1e, 0x00,
-0x01, 0x29, 0x01, 0x03, 0x26, 0x09, 0x01, 0x23,
+0x00, 0x2f, 0xfd, 0x06, 0x01, 0x13, 0x1e, 0x00,
+0x01, 0x28, 0x01, 0x03, 0x25, 0x09, 0x01, 0x22,
 0x00, 0x0c, 0x00, 0x07, 0x91, 0x36, 0x19, 0x08,
-0x00, 0x10, 0x50, 0x17, 0x21, 0x0c, 0x0f, 0x81,
-0x00, 0x23, 0x51, 0x87, 0x86, 0x78, 0x46, 0xf5,
+0x00, 0x10, 0x50, 0x16, 0x21, 0x0c, 0x0d, 0x91,
+      0x23, 0x51, 0x87, 0x86, 0x78, 0x46, 0xf5,
 0x00, 0x00, 0x09, 0xcc, 0xb7, 0xbd, 0x0c, 0xca,
 0xbf, 0xeb, 0x20
 };