diff --git a/src/com/android/contacts/calllog/CallLogNotificationsService.java b/src/com/android/contacts/calllog/CallLogNotificationsService.java
index eda11d6..6dd24aa 100644
--- a/src/com/android/contacts/calllog/CallLogNotificationsService.java
+++ b/src/com/android/contacts/calllog/CallLogNotificationsService.java
@@ -18,25 +18,55 @@
 
 import android.app.IntentService;
 import android.content.Intent;
+import android.net.Uri;
 import android.util.Log;
 
 /**
  * Provides operations for managing notifications.
  * <p>
- * At the moment, it only handle {@link #ACTION_MARK_NEW_CALLS_AS_OLD}, which marks all the new
- * items in the call log as old; this is called when a notification is dismissed.
+ * It handles the following actions:
+ * <ul>
+ * <li>{@link #ACTION_MARK_NEW_CALLS_AS_OLD}: marks all the new items in the call log as old; this
+ * is called when a notification is dismissed.</li>
+ * <li>{@link #ACTION_UPDATE_NOTIFICATIONS}: updates the content of the new items notification; it
+ * may include an optional extra {@link #EXTRA_NEW_VOICEMAIL_URI}, containing the URI of the new
+ * voicemail that has triggered this update (if any).</li>
+ * </ul>
  */
 public class CallLogNotificationsService extends IntentService {
     private static final String TAG = "CallLogNotificationsService";
 
-    // Action to mark all the new calls as old. Invoked when the notifications need to be cleared.
+    /**
+     * Action to mark all the new calls as old.
+     */
     public static final String ACTION_MARK_NEW_CALLS_AS_OLD =
-            "com.android.contacts.ACTION_MARK_NEW_CALLS_AS_OLD";
+            "com.android.contacts.calllog.MARK_NEW_CALLS_AS_OLD";
+
+    /**
+     * Action to update the notifications.
+     * <p>
+     * May include an optional extra {@link #EXTRA_NEW_VOICEMAIL_URI}.
+     */
+    public static final String ACTION_UPDATE_NOTIFICATIONS =
+            "com.android.contacts.calllog.UPDATE_NOTIFICATIONS";
+
+    /**
+     * Extra to included with {@link #ACTION_UPDATE_NOTIFICATIONS} to identify the new voicemail
+     * that triggered an update.
+     * <p>
+     * It must be a {@link Uri}.
+     */
+    public static final String EXTRA_NEW_VOICEMAIL_URI = "NEW_VOICEMAIL_URI";
 
     private CallLogQueryHandler mCallLogQueryHandler;
 
     public CallLogNotificationsService() {
         super("CallLogNotificationsService");
+    }
+
+    @Override
+    public void onCreate() {
+        super.onCreate();
         mCallLogQueryHandler = new CallLogQueryHandler(getContentResolver(), null /*listener*/);
     }
 
@@ -44,10 +74,11 @@
     protected void onHandleIntent(Intent intent) {
         if (ACTION_MARK_NEW_CALLS_AS_OLD.equals(intent.getAction())) {
             mCallLogQueryHandler.markNewCallsAsOld();
-            return;
+        } else if (ACTION_UPDATE_NOTIFICATIONS.equals(intent.getAction())) {
+            Uri voicemailUri = (Uri) intent.getParcelableExtra(EXTRA_NEW_VOICEMAIL_URI);
+            DefaultVoicemailNotifier.getInstance(this).updateNotification(voicemailUri);
         } else {
             Log.d(TAG, "onHandleIntent: could not handle: " + intent);
         }
     }
-
 }
diff --git a/src/com/android/contacts/calllog/CallLogReceiver.java b/src/com/android/contacts/calllog/CallLogReceiver.java
index a3ff1f2..14bfa64 100644
--- a/src/com/android/contacts/calllog/CallLogReceiver.java
+++ b/src/com/android/contacts/calllog/CallLogReceiver.java
@@ -16,9 +16,7 @@
 
 package com.android.contacts.calllog;
 
-import android.app.NotificationManager;
 import android.content.BroadcastReceiver;
-import android.content.ContentResolver;
 import android.content.Context;
 import android.content.Intent;
 import android.provider.VoicemailContract;
@@ -33,29 +31,20 @@
 public class CallLogReceiver extends BroadcastReceiver {
     private static final String TAG = "CallLogReceiver";
 
-    private VoicemailNotifier mNotifier;
-
     @Override
     public void onReceive(Context context, Intent intent) {
-        if (mNotifier == null) {
-            mNotifier = getNotifier(context);
-        }
         if (VoicemailContract.ACTION_NEW_VOICEMAIL.equals(intent.getAction())) {
-            mNotifier.notifyNewVoicemail(intent.getData());
+            Intent serviceIntent = new Intent(context, CallLogNotificationsService.class);
+            serviceIntent.setAction(CallLogNotificationsService.ACTION_UPDATE_NOTIFICATIONS);
+            serviceIntent.putExtra(
+                    CallLogNotificationsService.EXTRA_NEW_VOICEMAIL_URI, intent.getData());
+            context.startService(serviceIntent);
         } else if (Intent.ACTION_BOOT_COMPLETED.equals(intent.getAction())) {
-            mNotifier.updateNotification();
+            Intent serviceIntent = new Intent(context, CallLogNotificationsService.class);
+            serviceIntent.setAction(CallLogNotificationsService.ACTION_UPDATE_NOTIFICATIONS);
+            context.startService(serviceIntent);
         } else {
-            Log.d(TAG, "onReceive: could not handle: " + intent);
+            Log.w(TAG, "onReceive: could not handle: " + intent);
         }
     }
-
-    private VoicemailNotifier getNotifier(Context context) {
-        NotificationManager notificationManager =
-                (NotificationManager) context.getSystemService(Context.NOTIFICATION_SERVICE);
-        ContentResolver contentResolver = context.getContentResolver();
-        return new DefaultVoicemailNotifier(context, notificationManager,
-                DefaultVoicemailNotifier.createNewCallsQuery(contentResolver),
-                DefaultVoicemailNotifier.createNameLookupQuery(contentResolver),
-                DefaultVoicemailNotifier.createPhoneNumberHelper(context));
-    }
 }
diff --git a/src/com/android/contacts/calllog/DefaultVoicemailNotifier.java b/src/com/android/contacts/calllog/DefaultVoicemailNotifier.java
index bb0b0f3..1cf67c1 100644
--- a/src/com/android/contacts/calllog/DefaultVoicemailNotifier.java
+++ b/src/com/android/contacts/calllog/DefaultVoicemailNotifier.java
@@ -51,13 +51,30 @@
     /** The identifier of the notification of new voicemails. */
     private static final int NOTIFICATION_ID = 1;
 
+    /** The singleton instance of {@link DefaultVoicemailNotifier}. */
+    private static DefaultVoicemailNotifier sInstance;
+
     private final Context mContext;
     private final NotificationManager mNotificationManager;
     private final NewCallsQuery mNewCallsQuery;
     private final NameLookupQuery mNameLookupQuery;
     private final PhoneNumberHelper mPhoneNumberHelper;
 
-    public DefaultVoicemailNotifier(Context context,
+    /** Returns the singleton instance of the {@link DefaultVoicemailNotifier}. */
+    public static synchronized DefaultVoicemailNotifier getInstance(Context context) {
+        if (sInstance == null) {
+            NotificationManager notificationManager =
+                    (NotificationManager) context.getSystemService(Context.NOTIFICATION_SERVICE);
+            ContentResolver contentResolver = context.getContentResolver();
+            sInstance = new DefaultVoicemailNotifier(context, notificationManager,
+                    createNewCallsQuery(contentResolver),
+                    createNameLookupQuery(contentResolver),
+                    createPhoneNumberHelper(context));
+        }
+        return sInstance;
+    }
+
+    private DefaultVoicemailNotifier(Context context,
             NotificationManager notificationManager, NewCallsQuery newCallsQuery,
             NameLookupQuery nameLookupQuery, PhoneNumberHelper phoneNumberHelper) {
         mContext = context;
@@ -67,20 +84,9 @@
         mPhoneNumberHelper = phoneNumberHelper;
     }
 
-    @Override
-    public void notifyNewVoicemail(Uri newVoicemailUri) {
-        Log.d(TAG, "notifyNewVoicemail: " + newVoicemailUri);
-        updateNotification(newVoicemailUri);
-    }
-
-    @Override
-    public void updateNotification() {
-        Log.d(TAG, "updateNotification");
-        updateNotification(null);
-    }
-
     /** Updates the notification and notifies of the call with the given URI. */
-    private void updateNotification(Uri newCallUri) {
+    @Override
+    public void updateNotification(Uri newCallUri) {
         // Lookup the list of new voicemails to include in the notification.
         // TODO: Move this into a service, to avoid holding the receiver up.
         final NewCall[] newCalls = mNewCallsQuery.query();
diff --git a/src/com/android/contacts/calllog/VoicemailNotifier.java b/src/com/android/contacts/calllog/VoicemailNotifier.java
index 1ac949d..8d45486 100644
--- a/src/com/android/contacts/calllog/VoicemailNotifier.java
+++ b/src/com/android/contacts/calllog/VoicemailNotifier.java
@@ -23,17 +23,15 @@
  */
 public interface VoicemailNotifier {
     /**
-     * Notifies the user of a new voicemail.
+     * Updates the notification and clears it if there are no new voicemails.
+     * <p>
+     * If the given URI corresponds to a new voicemail, also notifies about it.
+     * <p>
+     * It is not safe to call this method from the main thread.
      *
-     * @param newVoicemailUri URI of the new voicemail record just inserted
+     * @param newCallUri URI of the new call, may be null
      */
-    public void notifyNewVoicemail(Uri newVoicemailUri);
-
-    /**
-     * Updates the notification and clears it if there are no new voicemails. Called when the phone
-     * just rebooted to put back notifications for anything the user has not acknowledged.
-     */
-    public void updateNotification();
+    public void updateNotification(Uri newCallUri);
 
     /** Clears the new voicemail notification. */
     public void clearNotification();