diff --git a/src/com/android/server/telecom/InCallController.java b/src/com/android/server/telecom/InCallController.java
index 9a53575..6e09291 100644
--- a/src/com/android/server/telecom/InCallController.java
+++ b/src/com/android/server/telecom/InCallController.java
@@ -1136,6 +1136,10 @@
 
     @Override
     public void onCallAdded(Call call) {
+        Log.i(this, "onCallAdded: %s", call);
+        // Track the call if we don't already know about it.
+        addCall(call);
+
         if (!isBoundAndConnectedToServices()) {
             Log.i(this, "onCallAdded: %s; not bound or connected.", call);
             // We are not bound, or we're not connected.
@@ -1148,10 +1152,6 @@
             mEmergencyCallHelper.maybeGrantTemporaryLocationPermission(call,
                     mCallsManager.getCurrentUserHandle());
 
-            Log.i(this, "onCallAdded: %s", call);
-            // Track the call if we don't already know about it.
-            addCall(call);
-
             Log.i(this, "mInCallServiceConnection isConnected=%b",
                     mInCallServiceConnection.isConnected());
 
diff --git a/tests/src/com/android/server/telecom/tests/InCallControllerTests.java b/tests/src/com/android/server/telecom/tests/InCallControllerTests.java
index 3d387a8..08752f0 100644
--- a/tests/src/com/android/server/telecom/tests/InCallControllerTests.java
+++ b/tests/src/com/android/server/telecom/tests/InCallControllerTests.java
@@ -52,10 +52,12 @@
 import android.app.UiModeManager;
 import android.content.AttributionSource;
 import android.content.AttributionSourceState;
+import android.content.BroadcastReceiver;
 import android.content.ComponentName;
 import android.content.ContentResolver;
 import android.content.Context;
 import android.content.Intent;
+import android.content.IntentFilter;
 import android.content.PermissionChecker;
 import android.content.ServiceConnection;
 import android.content.pm.ApplicationInfo;
@@ -65,6 +67,7 @@
 import android.content.pm.ServiceInfo;
 import android.content.res.Resources;
 import android.compat.testing.PlatformCompatChangeRule;
+import android.net.Uri;
 import android.os.Binder;
 import android.os.Build;
 import android.os.Bundle;
@@ -118,6 +121,7 @@
 import org.mockito.quality.Strictness;
 import org.mockito.stubbing.Answer;
 
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.LinkedList;
 import java.util.List;
@@ -180,6 +184,7 @@
     private EmergencyCallHelper mEmergencyCallHelper;
     private SystemStateHelper.SystemStateListener mSystemStateListener;
     private CarModeTracker mCarModeTracker = spy(new CarModeTracker());
+    private BroadcastReceiver mRegisteredReceiver;
 
     private final int serviceBindingFlags = Context.BIND_AUTO_CREATE
         | Context.BIND_FOREGROUND_SERVICE | Context.BIND_ALLOW_BACKGROUND_ACTIVITY_STARTS
@@ -191,6 +196,7 @@
         super.setUp();
         MockitoAnnotations.initMocks(this);
         when(mMockCall.getAnalytics()).thenReturn(new Analytics.CallInfo());
+        when(mMockCall.getId()).thenReturn("TC@1");
         doReturn(mMockResources).when(mMockContext).getResources();
         doReturn(mMockAppOpsManager).when(mMockContext).getSystemService(AppOpsManager.class);
         doReturn(SYS_PKG).when(mMockResources).getString(
@@ -214,6 +220,12 @@
         mInCallController = new InCallController(mMockContext, mLock, mMockCallsManager,
                 mMockSystemStateHelper, mDefaultDialerCache, mTimeoutsAdapter,
                 mEmergencyCallHelper, mCarModeTracker, mClockProxy);
+        // Capture the broadcast receiver registered.
+        doAnswer(invocation -> {
+            mRegisteredReceiver = invocation.getArgument(0);
+            return null;
+        }).when(mMockContext).registerReceiver(any(BroadcastReceiver.class),
+                any(IntentFilter.class));
 
         ArgumentCaptor<SystemStateHelper.SystemStateListener> systemStateListenerArgumentCaptor
                 = ArgumentCaptor.forClass(SystemStateHelper.SystemStateListener.class);
@@ -756,6 +768,104 @@
     }
 
     /**
+     * Tests a case where InCallController DOES NOT bind to ANY InCallServices when the call is
+     * first added, but then one becomes available after the call starts.  This test was originally
+     * added to reproduce a bug which would cause the call id mapper in the InCallController to not
+     * track a newly added call unless something was bound when the call was first added.
+     * @throws Exception
+     */
+    @MediumTest
+    @Test
+    public void testNoInitialBinding() throws Exception {
+        Bundle callExtras = new Bundle();
+        callExtras.putBoolean("whatever", true);
+
+        // Make a basic call
+        when(mMockCallsManager.getCurrentUserHandle()).thenReturn(mUserHandle);
+        when(mMockContext.getPackageManager()).thenReturn(mMockPackageManager);
+        when(mMockCallsManager.isInEmergencyCall()).thenReturn(true);
+        when(mMockCall.isEmergencyCall()).thenReturn(true);
+        when(mMockCall.isIncoming()).thenReturn(false);
+        when(mMockCall.getTargetPhoneAccount()).thenReturn(PA_HANDLE);
+        when(mMockCall.getIntentExtras()).thenReturn(callExtras);
+        when(mMockCall.isExternalCall()).thenReturn(false);
+        when(mMockCall.isSelfManaged()).thenReturn(true);
+        when(mMockCall.visibleToInCallService()).thenReturn(true);
+
+        // Dialer doesn't handle these calls, but non-UI ICS does.
+        when(mDefaultDialerCache.getDefaultDialerApplication(CURRENT_USER_ID))
+                .thenReturn(DEF_PKG);
+        ArgumentCaptor<ServiceConnection> serviceConnectionCaptor =
+                ArgumentCaptor.forClass(ServiceConnection.class);
+        when(mMockContext.bindServiceAsUser(any(Intent.class), serviceConnectionCaptor.capture(),
+                eq(serviceBindingFlags),
+                eq(mUserHandle))).thenReturn(true);
+        when(mTimeoutsAdapter.getEmergencyCallbackWindowMillis(any(ContentResolver.class)))
+                .thenReturn(300_000L);
+
+        // Setup package manager; there is a dialer and disable non-ui ICS
+        when(mMockPackageManager.queryIntentServicesAsUser(
+                any(Intent.class), anyInt(), anyInt())).thenReturn(
+                Arrays.asList(
+                        getDefResolveInfo(false /* externalCalls */, false /* selfMgd */),
+                        getNonUiResolveinfo(true /* selfManaged */,
+                                false /* isEnabled */)
+                )
+        );
+        when(mMockPackageManager
+                .getComponentEnabledSetting(new ComponentName(DEF_PKG, DEF_CLASS)))
+                .thenReturn(PackageManager.COMPONENT_ENABLED_STATE_ENABLED);
+        when(mMockPackageManager
+                .getComponentEnabledSetting(new ComponentName(NONUI_PKG, NONUI_CLASS)))
+                .thenReturn(PackageManager.COMPONENT_ENABLED_STATE_DISABLED);
+
+        // Add the call.
+        mInCallController.onCallAdded(mMockCall);
+
+        // There will be 4 calls for the various types of ICS; this is normal.
+        verify(mMockPackageManager, times(4)).queryIntentServicesAsUser(
+                any(Intent.class),
+                eq(PackageManager.GET_META_DATA | PackageManager.MATCH_DISABLED_COMPONENTS),
+                eq(CURRENT_USER_ID));
+
+        // Verify no bind at this point
+        ArgumentCaptor<Intent> bindIntentCaptor = ArgumentCaptor.forClass(Intent.class);
+        verify(mMockContext, never()).bindServiceAsUser(
+                bindIntentCaptor.capture(),
+                any(ServiceConnection.class),
+                eq(serviceBindingFlags),
+                eq(mUserHandle));
+
+        // Setup mocks to enable non-ui ICS
+        when(mMockPackageManager.queryIntentServicesAsUser(
+                any(Intent.class), anyInt(), anyInt())).thenReturn(
+                Arrays.asList(
+                        getDefResolveInfo(false /* externalCalls */, false /* selfMgd */),
+                        getNonUiResolveinfo(true /* selfManaged */,
+                                true /* isEnabled */)
+                )
+        );
+        when(mMockPackageManager
+                .getComponentEnabledSetting(new ComponentName(NONUI_PKG, NONUI_CLASS)))
+                .thenReturn(PackageManager.COMPONENT_ENABLED_STATE_ENABLED);
+
+        // Emulate a late enable of the non-ui ICS
+        Intent packageUpdated = new Intent(Intent.ACTION_PACKAGE_CHANGED);
+        packageUpdated.setData(Uri.fromParts("package", NONUI_PKG, null));
+        packageUpdated.putExtra(Intent.EXTRA_CHANGED_COMPONENT_NAME_LIST,
+                new String[] {NONUI_CLASS});
+        packageUpdated.putExtra(Intent.EXTRA_UID, NONUI_UID);
+        mRegisteredReceiver.onReceive(mMockContext, packageUpdated);
+
+        // Make sure we bound to it.
+        verify(mMockContext, times(1)).bindServiceAsUser(
+                bindIntentCaptor.capture(),
+                any(ServiceConnection.class),
+                eq(serviceBindingFlags),
+                any(UserHandle.class));
+    }
+
+    /**
      * Ensures that the {@link InCallController} will bind to an {@link InCallService} which
      * supports external calls.
      */
@@ -1379,13 +1489,17 @@
     }
 
     private ResolveInfo getNonUiResolveinfo(boolean supportsSelfManaged) {
+        return getNonUiResolveinfo(supportsSelfManaged, true /* isEnabled */);
+    }
+
+    private ResolveInfo getNonUiResolveinfo(boolean supportsSelfManaged, boolean isEnabled) {
         return new ResolveInfo() {{
             serviceInfo = new ServiceInfo();
             serviceInfo.packageName = NONUI_PKG;
             serviceInfo.name = NONUI_CLASS;
             serviceInfo.applicationInfo = new ApplicationInfo();
             serviceInfo.applicationInfo.uid = NONUI_UID;
-            serviceInfo.enabled = true;
+            serviceInfo.enabled = isEnabled;
             serviceInfo.permission = Manifest.permission.BIND_INCALL_SERVICE;
             serviceInfo.metaData = new Bundle();
             if (supportsSelfManaged) {