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);