diff --git a/contrib/perf.py b/contrib/perf.py
--- a/contrib/perf.py
+++ b/contrib/perf.py
@@ -95,7 +95,7 @@ def perfaddremove(ui, repo):
         oldquiet = repo.ui.quiet
         repo.ui.quiet = True
         matcher = scmutil.match(repo[None])
-        timer(lambda: scmutil.addremove(repo, matcher, dry_run=True))
+        timer(lambda: scmutil.addremove(repo, matcher, "", dry_run=True))
     finally:
         repo.ui.quiet = oldquiet
         fm.end()
diff --git a/hgext/largefiles/overrides.py b/hgext/largefiles/overrides.py
--- a/hgext/largefiles/overrides.py
+++ b/hgext/largefiles/overrides.py
@@ -1084,10 +1084,10 @@ def overridesummary(orig, ui, repo, *pat
     finally:
         repo.lfstatus = False
 
-def scmutiladdremove(orig, repo, matcher, opts={}, dry_run=None,
+def scmutiladdremove(orig, repo, matcher, prefix, opts={}, dry_run=None,
                      similarity=None):
     if not lfutil.islfilesrepo(repo):
-        return orig(repo, matcher, opts, dry_run, similarity)
+        return orig(repo, matcher, prefix, opts, dry_run, similarity)
     # Get the list of missing largefiles so we can remove them
     lfdirstate = lfutil.openlfdirstate(repo.ui, repo)
     unsure, s = lfdirstate.status(match_.always(repo.root, repo.getcwd()), [],
@@ -1107,7 +1107,7 @@ def scmutiladdremove(orig, repo, matcher
     # function to take care of the rest.  Make sure it doesn't do anything with
     # largefiles by passing a matcher that will ignore them.
     matcher = composenormalfilematcher(matcher, repo[None].manifest())
-    return orig(repo, matcher, opts, dry_run, similarity)
+    return orig(repo, matcher, prefix, opts, dry_run, similarity)
 
 # Calling purge with --all will cause the largefiles to be deleted.
 # Override repo.status to prevent this from happening.
diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -2202,7 +2202,7 @@ def commit(ui, repo, commitfunc, pats, o
     # extract addremove carefully -- this function can be called from a command
     # that doesn't support addremove
     if opts.get('addremove'):
-        if scmutil.addremove(repo, matcher, opts) != 0:
+        if scmutil.addremove(repo, matcher, "", opts) != 0:
             raise util.Abort(
                 _("failed to mark all new/missing files as added/removed"))
 
diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -236,7 +236,7 @@ def addremove(ui, repo, *pats, **opts):
     if sim < 0 or sim > 100:
         raise util.Abort(_('similarity must be between 0 and 100'))
     matcher = scmutil.match(repo[None], pats, opts)
-    return scmutil.addremove(repo, matcher, opts, similarity=sim / 100.0)
+    return scmutil.addremove(repo, matcher, "", opts, similarity=sim / 100.0)
 
 @command('^annotate|blame',
     [('r', 'rev', '', _('annotate the specified revision'), _('REV')),
diff --git a/mercurial/help/subrepos.txt b/mercurial/help/subrepos.txt
--- a/mercurial/help/subrepos.txt
+++ b/mercurial/help/subrepos.txt
@@ -94,7 +94,9 @@ Interaction with Mercurial Commands
     -S/--subrepos, or setting "ui.commitsubrepos=True" in a
     configuration file (see :hg:`help config`).  After there are no
     longer any modified subrepositories, it records their state and
-    finally commits it in the parent repository.
+    finally commits it in the parent repository.  The --addremove
+    option also honors the -S/--subrepos option.  However, Git and
+    Subversion subrepositories will print a warning and abort.
 
 :diff: diff does not recurse in subrepos unless -S/--subrepos is
     specified. Changes are displayed as usual, on the subrepositories
diff --git a/mercurial/scmutil.py b/mercurial/scmutil.py
--- a/mercurial/scmutil.py
+++ b/mercurial/scmutil.py
@@ -713,13 +713,28 @@ def matchfiles(repo, files):
     '''Return a matcher that will efficiently match exactly these files.'''
     return matchmod.exact(repo.root, repo.getcwd(), files)
 
-def addremove(repo, matcher, opts={}, dry_run=None, similarity=None):
+def addremove(repo, matcher, prefix, opts={}, dry_run=None, similarity=None):
     m = matcher
     if dry_run is None:
         dry_run = opts.get('dry_run')
     if similarity is None:
         similarity = float(opts.get('similarity') or 0)
 
+    ret = 0
+    join = lambda f: os.path.join(prefix, f)
+
+    wctx = repo[None]
+    for subpath in sorted(wctx.substate):
+        if opts.get('subrepos'):
+            sub = wctx.sub(subpath)
+            try:
+                submatch = matchmod.narrowmatcher(subpath, m)
+                if sub.addremove(submatch, prefix, opts, dry_run, similarity):
+                    ret = 1
+            except error.LookupError:
+                repo.ui.status(_("skipping missing subrepository: %s\n")
+                                 % join(subpath))
+
     rejected = []
     origbad = m.bad
     def badfn(f, msg):
@@ -737,9 +752,9 @@ def addremove(repo, matcher, opts={}, dr
     for abs in sorted(toprint):
         if repo.ui.verbose or not m.exact(abs):
             if abs in unknownset:
-                status = _('adding %s\n') % m.uipath(abs)
+                status = _('adding %s\n') % m.uipath(join(abs))
             else:
-                status = _('removing %s\n') % m.uipath(abs)
+                status = _('removing %s\n') % m.uipath(join(abs))
             repo.ui.status(status)
 
     renames = _findrenames(repo, m, added + unknown, removed + deleted,
@@ -751,7 +766,7 @@ def addremove(repo, matcher, opts={}, dr
     for f in rejected:
         if f in m.files():
             return 1
-    return 0
+    return ret
 
 def marktouched(repo, files, similarity=0.0):
     '''Assert that files have somehow been operated upon. files are relative to
diff --git a/mercurial/subrepo.py b/mercurial/subrepo.py
--- a/mercurial/subrepo.py
+++ b/mercurial/subrepo.py
@@ -437,6 +437,10 @@ class abstractsubrepo(object):
     def add(self, ui, match, dryrun, listsubrepos, prefix, explicitonly):
         return []
 
+    def addremove(self, matcher, prefix, opts, dry_run, similarity):
+        self._ui.warn("%s: %s" % (prefix, _("addremove is not supported")))
+        return 1
+
     def cat(self, ui, match, prefix, **opts):
         return 1
 
@@ -619,6 +623,11 @@ class hgsubrepo(abstractsubrepo):
         return cmdutil.add(ui, self._repo, match, dryrun, listsubrepos,
                            os.path.join(prefix, self._path), explicitonly)
 
+    def addremove(self, m, prefix, opts, dry_run, similarity):
+        return scmutil.addremove(self._repo, m,
+                                 os.path.join(prefix, self._path), opts,
+                                 dry_run, similarity)
+
     @annotatesubrepoerror
     def cat(self, ui, match, prefix, **opts):
         rev = self._state[1]
diff --git a/tests/test-subrepo-deep-nested-change.t b/tests/test-subrepo-deep-nested-change.t
--- a/tests/test-subrepo-deep-nested-change.t
+++ b/tests/test-subrepo-deep-nested-change.t
@@ -106,8 +106,8 @@ Check that deep archiving works
   $ hg --config extensions.largefiles=! add sub1/sub2/test.txt
   $ mkdir sub1/sub2/folder
   $ echo 'subfolder' > sub1/sub2/folder/test.txt
-  $ hg --config extensions.largefiles=! add sub1/sub2/folder/test.txt
-  $ hg ci -Sm "add test.txt"
+  $ hg ci -ASm "add test.txt"
+  adding sub1/sub2/folder/test.txt (glob)
   committing subrepository sub1
   committing subrepository sub1/sub2 (glob)
 
@@ -128,6 +128,15 @@ Check that deep archiving works
   R sub1/.hgsubstate
   R sub1/sub2/folder/test.txt
   $ hg update -Cq
+  $ rm sub1/sub2/folder/test.txt
+  $ rm sub1/sub2/test.txt
+  $ hg ci -ASm "remove test.txt"
+  removing sub1/sub2/folder/test.txt (glob)
+  removing sub1/sub2/test.txt (glob)
+  committing subrepository sub1
+  committing subrepository sub1/sub2 (glob)
+  $ hg rollback -q
+  $ hg up -Cq
 
   $ hg --config extensions.largefiles=! archive -S ../archive_all
   $ find ../archive_all | sort