diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -298,7 +298,8 @@ def addremove(repo, pats=[], opts={}, dr
         dry_run = opts.get('dry_run')
     if similarity is None:
         similarity = float(opts.get('similarity') or 0)
-    unknown, deleted = [], []
+    # we'd use status here, except handling of symlinks and ignore is tricky
+    added, unknown, deleted, removed = [], [], [], []
     audit_path = util.path_auditor(repo.root)
     m = match(repo, pats, opts)
     for abs in repo.walk(m):
@@ -314,16 +315,22 @@ def addremove(repo, pats=[], opts={}, dr
             unknown.append(abs)
             if repo.ui.verbose or not exact:
                 repo.ui.status(_('adding %s\n') % ((pats and rel) or abs))
-        if repo.dirstate[abs] != 'r' and (not good or not util.lexists(target)
+        elif repo.dirstate[abs] != 'r' and (not good or not util.lexists(target)
             or (os.path.isdir(target) and not os.path.islink(target))):
             deleted.append(abs)
             if repo.ui.verbose or not exact:
                 repo.ui.status(_('removing %s\n') % ((pats and rel) or abs))
+        # for finding renames
+        elif repo.dirstate[abs] == 'r':
+            removed.append(abs)
+        elif repo.dirstate[abs] == 'a':
+            added.append(abs)
     if not dry_run:
         repo.remove(deleted)
         repo.add(unknown)
     if similarity > 0:
-        for old, new, score in findrenames(repo, unknown, deleted, similarity):
+        for old, new, score in findrenames(repo, added + unknown,
+                                           removed + deleted, similarity):
             if repo.ui.verbose or not m.exact(old) or not m.exact(new):
                 repo.ui.status(_('recording removal of %s as rename to %s '
                                  '(%d%% similar)\n') %
diff --git a/tests/test-addremove b/tests/test-addremove
--- a/tests/test-addremove
+++ b/tests/test-addremove
@@ -22,5 +22,6 @@ hg commit -Ama
 mv a b
 rm c
 echo d > d
+hg addremove -n -s 50 # issue 1696
 hg addremove -s 50
 hg commit -mb
diff --git a/tests/test-addremove.out b/tests/test-addremove.out
--- a/tests/test-addremove.out
+++ b/tests/test-addremove.out
@@ -15,3 +15,8 @@ adding b
 removing c
 adding d
 recording removal of a as rename to b (100% similar)
+removing a
+adding b
+removing c
+adding d
+recording removal of a as rename to b (100% similar)