diff --git a/src/com/android/contacts/calllog/CallLogFragment.java b/src/com/android/contacts/calllog/CallLogFragment.java
index 0713e0e..1ec3602 100644
--- a/src/com/android/contacts/calllog/CallLogFragment.java
+++ b/src/com/android/contacts/calllog/CallLogFragment.java
@@ -978,7 +978,7 @@
     @Override
     public void onStop() {
         super.onStop();
-        resetNewCallsFlag();
+        updateOnExit();
     }
 
     @Override
@@ -988,10 +988,6 @@
         mAdapter.changeCursor(null);
     }
 
-    private void resetNewCallsFlag() {
-        mCallLogQueryHandler.markNewCallsAsOld();
-    }
-
     private void startCallsQuery() {
         mAdapter.setLoading(true);
         mCallLogQueryHandler.fetchAllCalls();
@@ -1130,6 +1126,10 @@
         if (visible && isResumed()) {
             refreshData();
         }
+
+        if (!visible) {
+            updateOnExit();
+        }
     }
 
     /** Requests updates to the data to be shown. */
@@ -1140,11 +1140,7 @@
         startCallsQuery();
         startVoicemailStatusQuery();
         mAdapter.mPreDrawListener = null; // Let it restart the thread after next draw
-        // We don't want to remove notification when keyguard is on because the user has likely not
-        // seen the new call yet.
-        if (!mKeyguardManager.inKeyguardRestrictedInputMode()) {
-            removeMissedCallNotifications();
-        }
+        updateOnEntry();
     }
 
     /** Removes the missed call notifications. */
@@ -1162,4 +1158,36 @@
             Log.e(TAG, "Failed to clear missed calls notification due to remote exception");
         }
     }
+
+    /** Updates call data and notification state while leaving the call log tab. */
+    private void updateOnExit() {
+        updateOnTransition(false);
+    }
+
+    /** Updates call data and notification state while entering the call log tab. */
+    private void updateOnEntry() {
+        updateOnTransition(true);
+    }
+
+    private void updateOnTransition(boolean onEntry) {
+        // We don't want to update any call data when keyguard is on because the user has likely not
+        // seen the new calls yet.
+        if (!mKeyguardManager.inKeyguardRestrictedInputMode()) {
+            // On either of the transitions we reset the new flag and update the notifications.
+            // While exiting we additionally consume all missed calls (by marking them as read).
+            // This will ensure that they no more appear in the "new" section when we return back.
+            mCallLogQueryHandler.markNewCallsAsOld();
+            if (!onEntry) {
+                mCallLogQueryHandler.markMissedCallsAsRead();
+            }
+            removeMissedCallNotifications();
+            updateVoicemailNotifications();
+        }
+    }
+
+    private void updateVoicemailNotifications() {
+        Intent serviceIntent = new Intent(getActivity(), CallLogNotificationsService.class);
+        serviceIntent.setAction(CallLogNotificationsService.ACTION_UPDATE_NOTIFICATIONS);
+        getActivity().startService(serviceIntent);
+    }
 }
diff --git a/src/com/android/contacts/calllog/CallLogQueryHandler.java b/src/com/android/contacts/calllog/CallLogQueryHandler.java
index 68ac63a..b4e4248 100644
--- a/src/com/android/contacts/calllog/CallLogQueryHandler.java
+++ b/src/com/android/contacts/calllog/CallLogQueryHandler.java
@@ -51,9 +51,12 @@
     private static final int QUERY_OLD_CALLS_TOKEN = 54;
     /** The token for the query to mark all missed calls as old after seeing the call log. */
     private static final int UPDATE_MARK_AS_OLD_TOKEN = 55;
+    /** The token for the query to mark all missed calls as read after seeing the call log. */
+    private static final int UPDATE_MARK_MISSED_CALL_AS_READ_TOKEN = 56;
 
     /** The token for the query to fetch voicemail status messages. */
-    private static final int QUERY_VOICEMAIL_STATUS_TOKEN = 56;
+    private static final int QUERY_VOICEMAIL_STATUS_TOKEN = 57;
+
 
     private final WeakReference<Listener> mListener;
 
@@ -149,14 +152,11 @@
 
     /** Fetches the list of calls in the call log, either the new one or the old ones. */
     private void fetchCalls(int token, boolean isNew, boolean voicemailOnly) {
-        // We need to check for NULL explicitly otherwise entries with where NEW or READ are NULL
+        // We need to check for NULL explicitly otherwise entries with where READ is NULL
         // may not match either the query or its negation.
-        String selection =
-                String.format(
-                        "(%s IS NOT NULL AND %s = 1 AND (%s = ? OR %s = ?)) OR " +
-                        "(%s IS NOT NULL AND %s = 0)",
-                        Calls.NEW, Calls.NEW, Calls.TYPE, Calls.TYPE, Calls.IS_READ, Calls.IS_READ);
-        final String[] selectionArgs;
+        // We consider the calls that are not yet consumed (i.e. IS_READ = 0) as "new".
+        String selection = String.format("%s IS NOT NULL AND %s = 0", Calls.IS_READ, Calls.IS_READ);
+        String[] selectionArgs = null;
         if (!isNew) {
             // Negate the query.
             selection = String.format("NOT (%s)", selection);
@@ -165,13 +165,6 @@
             // Add a clause to fetch only items of type voicemail.
             selection = String.format("(%s) AND (%s = ?)", selection, Calls.TYPE);
             selectionArgs = new String[]{
-                    Integer.toString(Calls.MISSED_TYPE),
-                    Integer.toString(Calls.VOICEMAIL_TYPE),
-                    Integer.toString(Calls.VOICEMAIL_TYPE),
-            };
-        } else {
-            selectionArgs = new String[]{
-                    Integer.toString(Calls.MISSED_TYPE),
                     Integer.toString(Calls.VOICEMAIL_TYPE),
             };
         }
@@ -199,6 +192,21 @@
                 values, where.toString(), null);
     }
 
+    /** Updates all missed calls to mark them as read. */
+    public void markMissedCallsAsRead() {
+        // Mark all "new" calls as not new anymore.
+        StringBuilder where = new StringBuilder();
+        where.append(Calls.IS_READ).append(" = 0");
+        where.append(" AND ");
+        where.append(Calls.TYPE).append(" = ").append(Calls.MISSED_TYPE);
+
+        ContentValues values = new ContentValues(1);
+        values.put(Calls.IS_READ, "1");
+
+        startUpdate(UPDATE_MARK_MISSED_CALL_AS_READ_TOKEN, null, Calls.CONTENT_URI, values,
+                where.toString(), null);
+    }
+
     /**
      * Invalidate the current list of calls.
      * <p>