diff --git a/src/com/android/telecomm/CallServiceAdapter.java b/src/com/android/telecomm/CallServiceAdapter.java
index e30d338..f95953a 100644
--- a/src/com/android/telecomm/CallServiceAdapter.java
+++ b/src/com/android/telecomm/CallServiceAdapter.java
@@ -23,7 +23,9 @@
 import com.android.internal.telecomm.ICallServiceAdapter;
 import com.google.android.collect.Sets;
 import com.google.common.base.Strings;
+import com.google.common.collect.ImmutableList;
 
+import java.util.Collections;
 import java.util.Set;
 
 /**
@@ -222,6 +224,35 @@
     }
 
     /**
+     * Called when the associated call service dies.
+     */
+    void handleCallServiceDeath() {
+        if (!mPendingIncomingCallIds.isEmpty()) {
+            // Here and in the for loop below, we need to iterate through a copy because the code
+            // inside the loop will modify the original list.
+            for (String callId : ImmutableList.copyOf(mPendingIncomingCallIds)) {
+                mIncomingCallsManager.handleFailedIncomingCall(callId);
+            }
+
+            if (!mPendingIncomingCallIds.isEmpty()) {
+                Log.wtf(this, "Pending incoming calls did not get cleared.");
+                mPendingIncomingCallIds.clear();
+            }
+        }
+
+        if (!mPendingOutgoingCallIds.isEmpty()) {
+            for (String callId : ImmutableList.copyOf(mPendingOutgoingCallIds)) {
+                mOutgoingCallsManager.handleFailedCallAttempt(callId, "Call service disconnected.");
+            }
+
+            if (!mPendingOutgoingCallIds.isEmpty()) {
+                Log.wtf(this, "Pending outgoing calls did not get cleared.");
+                mPendingOutgoingCallIds.clear();
+            }
+        }
+    }
+
+    /**
      * Throws an IllegalArgumentException if the specified call ID is invalid.
      *
      * @param callId The call ID to check.
diff --git a/src/com/android/telecomm/CallServiceWrapper.java b/src/com/android/telecomm/CallServiceWrapper.java
index 426a019..46e99cb 100644
--- a/src/com/android/telecomm/CallServiceWrapper.java
+++ b/src/com/android/telecomm/CallServiceWrapper.java
@@ -85,6 +85,7 @@
      * @param errorCallback The callback to invoke upon failure.
      */
     void isCompatibleWith(final CallInfo callInfo, final Runnable errorCallback) {
+        Log.d(this, "isCompatibleWith(%s) via %s.", callInfo, getComponentName());
         BindCallback callback = new BindCallback() {
             @Override public void onSuccess() {
                 if (isServiceValid("isCompatibleWith")) {
@@ -113,6 +114,7 @@
      * @param errorCallback The callback to invoke upon failure.
      */
     void call(final CallInfo callInfo, final Runnable errorCallback) {
+        Log.d(this, "call(%s) via %s.", callInfo, getComponentName());
         BindCallback callback = new BindCallback() {
             @Override public void onSuccess() {
                 String callId = callInfo.getId();
@@ -181,6 +183,7 @@
             final Bundle extras,
             final Runnable errorCallback) {
 
+        Log.d(this, "setIncomingCall(%s) via %s.", callId, getComponentName());
         BindCallback callback = new BindCallback() {
             @Override public void onSuccess() {
                 if (isServiceValid("setIncomingCallId")) {
@@ -257,7 +260,17 @@
 
     /** {@inheritDoc} */
     @Override protected void setServiceInterface(IBinder binder) {
-        mServiceInterface = ICallService.Stub.asInterface(binder);
-        setCallServiceAdapter(mAdapter);
+        if (binder == null) {
+            // We have lost our service connection. Notify the world that this call service is done.
+            // We must notify the adapter before CallsManager. The adapter will force any pending
+            // outgoing calls to try the next call service. This needs to happen before CallsManager
+            // tries to clean up any calls still associated with this call service.
+            mAdapter.handleCallServiceDeath();
+            CallsManager.getInstance().handleCallServiceDeath(this);
+            mServiceInterface = null;
+        } else {
+            mServiceInterface = ICallService.Stub.asInterface(binder);
+            setCallServiceAdapter(mAdapter);
+        }
     }
 }
diff --git a/src/com/android/telecomm/CallsManager.java b/src/com/android/telecomm/CallsManager.java
index 92c247e..36fbf77 100644
--- a/src/com/android/telecomm/CallsManager.java
+++ b/src/com/android/telecomm/CallsManager.java
@@ -350,6 +350,21 @@
     }
 
     /**
+     * Cleans up any calls currently associated with the specified call service when the
+     * call-service binder disconnects unexpectedly.
+     *
+     * @param callService The call service that disconnected.
+     */
+    void handleCallServiceDeath(CallServiceWrapper callService) {
+        Preconditions.checkNotNull(callService);
+        for (Call call : ImmutableList.copyOf(mCalls.values())) {
+            if (call.getCallService() == callService) {
+                markCallAsDisconnected(call.getId());
+            }
+        }
+    }
+
+    /**
      * Adds the specified call to the main list of live calls.
      *
      * @param call The call to add.
diff --git a/src/com/android/telecomm/IncomingCallsManager.java b/src/com/android/telecomm/IncomingCallsManager.java
index 6edbbbf..0d98dc4 100644
--- a/src/com/android/telecomm/IncomingCallsManager.java
+++ b/src/com/android/telecomm/IncomingCallsManager.java
@@ -63,7 +63,7 @@
 
         Runnable errorCallback = new Runnable() {
             @Override public void run() {
-                handleFailedIncomingCall(call);
+                handleFailedIncomingCall(callId);
             }
         };
 
@@ -89,12 +89,13 @@
     /**
      * Notifies switchboard of the failed incoming call after removing it from the pending list.
      *
-     * @param call The call.
+     * @param callId The ID of the call.
      */
-    private void handleFailedIncomingCall(Call call) {
+    void handleFailedIncomingCall(String callId) {
         ThreadUtil.checkOnMainThread();
 
-        if (mPendingIncomingCalls.remove(call.getId()) != null) {
+        Call call = mPendingIncomingCalls.remove(callId);
+        if (call != null) {
             Log.i(this, "Failed to get details for incoming call %s", call);
             // The call was found still waiting for details. Consider it failed.
             mSwitchboard.handleFailedIncomingCall(call);