diff --git a/Tethering/src/com/android/networkstack/tethering/Tethering.java b/Tethering/src/com/android/networkstack/tethering/Tethering.java
index 78f2afc..55c24d3 100644
--- a/Tethering/src/com/android/networkstack/tethering/Tethering.java
+++ b/Tethering/src/com/android/networkstack/tethering/Tethering.java
@@ -123,6 +123,7 @@
 import android.text.TextUtils;
 import android.util.ArrayMap;
 import android.util.Log;
+import android.util.Pair;
 import android.util.SparseArray;
 
 import androidx.annotation.NonNull;
@@ -267,6 +268,9 @@
     private String mConfiguredEthernetIface;
     private EthernetCallback mEthernetCallback;
     private SettingsObserver mSettingsObserver;
+    private BluetoothPan mBluetoothPan;
+    private PanServiceListener mBluetoothPanListener;
+    private ArrayList<Pair<Boolean, IIntResultListener>> mPendingPanRequests;
 
     public Tethering(TetheringDependencies deps) {
         mLog.mark("Tethering.constructed");
@@ -276,6 +280,11 @@
         mLooper = mDeps.getTetheringLooper();
         mNotificationUpdater = mDeps.getNotificationUpdater(mContext, mLooper);
 
+        // This is intended to ensrure that if something calls startTethering(bluetooth) just after
+        // bluetooth is enabled. Before onServiceConnected is called, store the calls into this
+        // list and handle them as soon as onServiceConnected is called.
+        mPendingPanRequests = new ArrayList<>();
+
         mTetherStates = new ArrayMap<>();
         mConnectedClientsTracker = new ConnectedClientsTracker();
 
@@ -701,35 +710,82 @@
             return;
         }
 
-        adapter.getProfileProxy(mContext, new ServiceListener() {
-            @Override
-            public void onServiceDisconnected(int profile) { }
+        if (mBluetoothPanListener != null && mBluetoothPanListener.isConnected()) {
+            // The PAN service is connected. Enable or disable bluetooth tethering.
+            // When bluetooth tethering is enabled, any time a PAN client pairs with this
+            // host, bluetooth will bring up a bt-pan interface and notify tethering to
+            // enable IP serving.
+            setBluetoothTetheringSettings(mBluetoothPan, enable, listener);
+            return;
+        }
 
-            @Override
-            public void onServiceConnected(int profile, BluetoothProfile proxy) {
-                // Clear identify is fine because caller already pass tethering permission at
-                // ConnectivityService#startTethering()(or stopTethering) before the control comes
-                // here. Bluetooth will check tethering permission again that there is
-                // Context#getOpPackageName() under BluetoothPan#setBluetoothTethering() to get
-                // caller's package name for permission check.
-                // Calling BluetoothPan#setBluetoothTethering() here means the package name always
-                // be system server. If calling identity is not cleared, that package's uid might
-                // not match calling uid and end up in permission denied.
-                final long identityToken = Binder.clearCallingIdentity();
-                try {
-                    ((BluetoothPan) proxy).setBluetoothTethering(enable);
-                } finally {
-                    Binder.restoreCallingIdentity(identityToken);
+        // The reference of IIntResultListener should only exist when application want to start
+        // tethering but tethering is not bound to pan service yet. Even if the calling process
+        // dies, the referenice of IIntResultListener would still keep in mPendingPanRequests. Once
+        // tethering bound to pan service (onServiceConnected) or bluetooth just crash
+        // (onServiceDisconnected), all the references from mPendingPanRequests would be cleared.
+        mPendingPanRequests.add(new Pair(enable, listener));
+
+        // Bluetooth tethering is not a popular feature. To avoid bind to bluetooth pan service all
+        // the time but user never use bluetooth tethering. mBluetoothPanListener is created first
+        // time someone calls a bluetooth tethering method (even if it's just to disable tethering
+        // when it's already disabled) and never unset after that.
+        if (mBluetoothPanListener == null) {
+            mBluetoothPanListener = new PanServiceListener();
+            adapter.getProfileProxy(mContext, mBluetoothPanListener, BluetoothProfile.PAN);
+        }
+    }
+
+    private class PanServiceListener implements ServiceListener {
+        private boolean mIsConnected = false;
+
+        @Override
+        public void onServiceConnected(int profile, BluetoothProfile proxy) {
+            // Posting this to handling onServiceConnected in tethering handler thread may have
+            // race condition that bluetooth service may disconnected when tethering thread
+            // actaully handle onServiceconnected. If this race happen, calling
+            // BluetoothPan#setBluetoothTethering would silently fail. It is fine because pan
+            // service is unreachable and both bluetooth and bluetooth tethering settings are off.
+            mHandler.post(() -> {
+                mBluetoothPan = (BluetoothPan) proxy;
+                mIsConnected = true;
+
+                for (Pair<Boolean, IIntResultListener> request : mPendingPanRequests) {
+                    setBluetoothTetheringSettings(mBluetoothPan, request.first, request.second);
                 }
-                // TODO: Enabling bluetooth tethering can fail asynchronously here.
-                // We should figure out a way to bubble up that failure instead of sending success.
-                final int result = (((BluetoothPan) proxy).isTetheringOn() == enable)
-                        ? TETHER_ERROR_NO_ERROR
-                        : TETHER_ERROR_INTERNAL_ERROR;
-                sendTetherResult(listener, result, TETHERING_BLUETOOTH);
-                adapter.closeProfileProxy(BluetoothProfile.PAN, proxy);
-            }
-        }, BluetoothProfile.PAN);
+                mPendingPanRequests.clear();
+            });
+        }
+
+        @Override
+        public void onServiceDisconnected(int profile) {
+            mHandler.post(() -> {
+                // onServiceDisconnected means Bluetooth is off (or crashed) and is not
+                // reachable before next onServiceConnected.
+                mIsConnected = false;
+
+                for (Pair<Boolean, IIntResultListener> request : mPendingPanRequests) {
+                    sendTetherResult(request.second, TETHER_ERROR_SERVICE_UNAVAIL,
+                            TETHERING_BLUETOOTH);
+                }
+                mPendingPanRequests.clear();
+            });
+        }
+
+        public boolean isConnected() {
+            return mIsConnected;
+        }
+    }
+
+    private void setBluetoothTetheringSettings(@NonNull final BluetoothPan bluetoothPan,
+            final boolean enable, final IIntResultListener listener) {
+        bluetoothPan.setBluetoothTethering(enable);
+
+        // Enabling bluetooth tethering settings can silently fail. Send internal error if the
+        // result is not expected.
+        final int result = bluetoothPan.isTetheringOn() == enable
+                ? TETHER_ERROR_NO_ERROR : TETHER_ERROR_INTERNAL_ERROR;
+        sendTetherResult(listener, result, TETHERING_BLUETOOTH);
     }
 
     private int setEthernetTethering(final boolean enable) {
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
index f45768f..40d133a 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
@@ -2558,10 +2558,10 @@
     @Test
     public void testBluetoothTethering() throws Exception {
         final ResultListener result = new ResultListener(TETHER_ERROR_NO_ERROR);
-        when(mBluetoothAdapter.isEnabled()).thenReturn(true);
+        mockBluetoothSettings(true /* bluetoothOn */, true /* tetheringOn */);
         mTethering.startTethering(createTetheringRequestParcel(TETHERING_BLUETOOTH), result);
         mLooper.dispatchAll();
-        verifySetBluetoothTethering(true);
+        verifySetBluetoothTethering(true /* enable */, true /* bindToPanService */);
         result.assertHasResult();
 
         mTethering.interfaceAdded(TEST_BT_IFNAME);
@@ -2574,6 +2574,64 @@
         mLooper.dispatchAll();
         tetherResult.assertHasResult();
 
+        verifyNetdCommandForBtSetup();
+
+        // Turning tethering on a second time does not bind to the PAN service again, since it's
+        // already bound.
+        mockBluetoothSettings(true /* bluetoothOn */, true /* tetheringOn */);
+        final ResultListener secondResult = new ResultListener(TETHER_ERROR_NO_ERROR);
+        mTethering.startTethering(createTetheringRequestParcel(TETHERING_BLUETOOTH), secondResult);
+        mLooper.dispatchAll();
+        verifySetBluetoothTethering(true /* enable */, false /* bindToPanService */);
+        secondResult.assertHasResult();
+
+        mockBluetoothSettings(true /* bluetoothOn */, false /* tetheringOn */);
+        mTethering.stopTethering(TETHERING_BLUETOOTH);
+        mLooper.dispatchAll();
+        final ResultListener untetherResult = new ResultListener(TETHER_ERROR_NO_ERROR);
+        mTethering.untether(TEST_BT_IFNAME, untetherResult);
+        mLooper.dispatchAll();
+        untetherResult.assertHasResult();
+        verifySetBluetoothTethering(false /* enable */, false /* bindToPanService */);
+
+        verifyNetdCommandForBtTearDown();
+    }
+
+    @Test
+    public void testBluetoothServiceDisconnects() throws Exception {
+        final ResultListener result = new ResultListener(TETHER_ERROR_NO_ERROR);
+        mockBluetoothSettings(true /* bluetoothOn */, true /* tetheringOn */);
+        mTethering.startTethering(createTetheringRequestParcel(TETHERING_BLUETOOTH), result);
+        mLooper.dispatchAll();
+        ServiceListener panListener = verifySetBluetoothTethering(true /* enable */,
+                true /* bindToPanService */);
+        result.assertHasResult();
+
+        mTethering.interfaceAdded(TEST_BT_IFNAME);
+        mLooper.dispatchAll();
+
+        mTethering.interfaceStatusChanged(TEST_BT_IFNAME, false);
+        mTethering.interfaceStatusChanged(TEST_BT_IFNAME, true);
+        final ResultListener tetherResult = new ResultListener(TETHER_ERROR_NO_ERROR);
+        mTethering.tether(TEST_BT_IFNAME, IpServer.STATE_TETHERED, tetherResult);
+        mLooper.dispatchAll();
+        tetherResult.assertHasResult();
+
+        verifyNetdCommandForBtSetup();
+
+        panListener.onServiceDisconnected(BluetoothProfile.PAN);
+        mTethering.interfaceStatusChanged(TEST_BT_IFNAME, false);
+        mLooper.dispatchAll();
+
+        verifyNetdCommandForBtTearDown();
+    }
+
+    private void mockBluetoothSettings(boolean bluetoothOn, boolean tetheringOn) {
+        when(mBluetoothAdapter.isEnabled()).thenReturn(bluetoothOn);
+        when(mBluetoothPan.isTetheringOn()).thenReturn(tetheringOn);
+    }
+
+    private void verifyNetdCommandForBtSetup() throws Exception {
         verify(mNetd).tetherInterfaceAdd(TEST_BT_IFNAME);
         verify(mNetd).networkAddInterface(INetd.LOCAL_NET_ID, TEST_BT_IFNAME);
         verify(mNetd, times(2)).networkAddRoute(eq(INetd.LOCAL_NET_ID), eq(TEST_BT_IFNAME),
@@ -2584,39 +2642,41 @@
                 anyString(), anyString());
         verifyNoMoreInteractions(mNetd);
         reset(mNetd);
+    }
 
-        when(mBluetoothAdapter.isEnabled()).thenReturn(true);
-        mTethering.stopTethering(TETHERING_BLUETOOTH);
-        mLooper.dispatchAll();
-        final ResultListener untetherResult = new ResultListener(TETHER_ERROR_NO_ERROR);
-        mTethering.untether(TEST_BT_IFNAME, untetherResult);
-        mLooper.dispatchAll();
-        untetherResult.assertHasResult();
-        verifySetBluetoothTethering(false);
-
+    private void verifyNetdCommandForBtTearDown() throws Exception {
         verify(mNetd).tetherApplyDnsInterfaces();
         verify(mNetd).tetherInterfaceRemove(TEST_BT_IFNAME);
         verify(mNetd).networkRemoveInterface(INetd.LOCAL_NET_ID, TEST_BT_IFNAME);
         verify(mNetd).interfaceSetCfg(any(InterfaceConfigurationParcel.class));
         verify(mNetd).tetherStop();
         verify(mNetd).ipfwdDisableForwarding(TETHERING_NAME);
-        verifyNoMoreInteractions(mNetd);
     }
 
-    private void verifySetBluetoothTethering(final boolean enable) {
-        final ArgumentCaptor<ServiceListener> listenerCaptor =
-                ArgumentCaptor.forClass(ServiceListener.class);
+    // If bindToPanService is true, this function would return ServiceListener which could notify
+    // PanService is connected or disconnected.
+    private ServiceListener verifySetBluetoothTethering(final boolean enable,
+            final boolean bindToPanService) {
+        ServiceListener listener = null;
         verify(mBluetoothAdapter).isEnabled();
-        verify(mBluetoothAdapter).getProfileProxy(eq(mServiceContext), listenerCaptor.capture(),
-                eq(BluetoothProfile.PAN));
-        final ServiceListener listener = listenerCaptor.getValue();
-        when(mBluetoothPan.isTetheringOn()).thenReturn(enable);
-        listener.onServiceConnected(BluetoothProfile.PAN, mBluetoothPan);
+        if (bindToPanService) {
+            final ArgumentCaptor<ServiceListener> listenerCaptor =
+                    ArgumentCaptor.forClass(ServiceListener.class);
+            verify(mBluetoothAdapter).getProfileProxy(eq(mServiceContext), listenerCaptor.capture(),
+                    eq(BluetoothProfile.PAN));
+            listener = listenerCaptor.getValue();
+            listener.onServiceConnected(BluetoothProfile.PAN, mBluetoothPan);
+            mLooper.dispatchAll();
+        } else {
+            verify(mBluetoothAdapter, never()).getProfileProxy(eq(mServiceContext), any(),
+                    anyInt());
+        }
         verify(mBluetoothPan).setBluetoothTethering(enable);
         verify(mBluetoothPan).isTetheringOn();
-        verify(mBluetoothAdapter).closeProfileProxy(eq(BluetoothProfile.PAN), eq(mBluetoothPan));
         verifyNoMoreInteractions(mBluetoothAdapter, mBluetoothPan);
         reset(mBluetoothAdapter, mBluetoothPan);
+
+        return listener;
     }
 
     private void runDualStackUsbTethering(final String expectedIface) throws Exception {