diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -1098,6 +1098,30 @@
 
     repo.ui.debug(" future parents are %d and %d\n" % tuple(newps))
 
+    # If there are multiple merge base candidates, try to remove one of them.
+    # Prefer keeping obsoleted node with successor in destination. Otherwise we
+    # might re-introduce unwanted obsoleted changes. For example,
+    #
+    #     C      # rebase -r A+B+C -d D
+    #    /|      # Suppose A has content "+A", B has "+B", D has "+D".
+    #   A B   D  # replace: A is replaced by D
+    #
+    # B gets moved on top of D, A gets skipped, C gets moved on top of B':
+    #
+    #         C' # When choosing merge base for C, A and B are candidates.
+    #         |  # If we choose B, the difference between C and B are "+A",
+    #     C   B' # and C' will have the content "+A", which is suboptimal
+    #    /|   |  # because it re-introduces obsoleted content. If we choose
+    #   A B   D  # A as merge base, it works as expected - C' may be empty.
+    if all(b != nullrev for b in bases):
+        assert len(bases) == 2
+        preferred = [any(isancestor(s, dest) for s in successorrevs(repo, r))
+                     for r in bases]
+        if preferred == [False, True]:
+            bases.reverse()
+            if newps[1] != nullrev:
+                newps.reverse()
+
     # "rebasenode" updates to new p1, use the corresponding merge base.
     if bases[0] != nullrev:
         base = bases[0]
diff --git a/tests/test-rebase-obsolete.t b/tests/test-rebase-obsolete.t
--- a/tests/test-rebase-obsolete.t
+++ b/tests/test-rebase-obsolete.t
@@ -1069,10 +1069,8 @@
   rebasing 2:b18e25de2cf5 "D" (D)
   note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
   rebasing 5:66f1a38021c9 "F" (F tip)
-  warning: rebasing 5:66f1a38021c9 may include unwanted changes from 3:7fb047a69f22
+  note: rebase of 5:66f1a38021c9 created no changes to commit
   $ hg log -G
-  o  7:9ed45af61fa0 F
-  |
   o  6:8f47515dda15 D
   |
   | x    5:66f1a38021c9 F
@@ -1106,11 +1104,9 @@
   note: not rebasing 2:b18e25de2cf5 "D" (D), already in destination as 1:112478962961 "B"
   rebasing 3:7fb047a69f22 "E" (E)
   rebasing 5:66f1a38021c9 "F" (F tip)
-  warning: rebasing 5:66f1a38021c9 may include unwanted changes from 2:b18e25de2cf5
+  note: rebase of 5:66f1a38021c9 created no changes to commit
 
   $ hg log -G
-  o  7:502540f44880 F
-  |
   o  6:533690786a86 E
   |
   | x    5:66f1a38021c9 F
@@ -1127,6 +1123,121 @@
   
   $ cd ..
 
+Rebase merge where both parents have successors in destination
+
+  $ hg init p12-succ-in-dest
+  $ cd p12-succ-in-dest
+  $ hg debugdrawdag <<'EOS'
+  >   E   F
+  >  /|  /|  # replace: A -> C
+  > A B C D  # replace: B -> D
+  > | |
+  > X Y
+  > EOS
+  $ hg rebase -r A+B+E -d F
+  note: not rebasing 4:a3d17304151f "A" (A), already in destination as 0:96cc3511f894 "C"
+  note: not rebasing 5:b23a2cc00842 "B" (B), already in destination as 1:058c1e1fb10a "D"
+  rebasing 7:dac5d11c5a7d "E" (E tip)
+  warning: rebasing 7:dac5d11c5a7d may include unwanted changes from 3:59c792af609c, 5:b23a2cc00842
+  $ hg manifest -r tip
+  B
+  C
+  D
+  Y
+  $ hg log -G -T '{rev}:{node|short} {desc|firstline} +{file_adds}\n'
+  o  8:3306ff4ff997 E +B Y
+  |
+  | x    7:dac5d11c5a7d E +B Y
+  | |\
+  o \ \    6:e0c929a964ce F +C
+  |\ \ \
+  | | | x  5:b23a2cc00842 B +B
+  | | | |
+  | | x |  4:a3d17304151f A +A
+  | | | |
+  | | | o  3:59c792af609c Y +Y
+  | | |
+  | | o  2:ba2b7fa7166d X +X
+  | |
+  | o  1:058c1e1fb10a D +D
+  |
+  o  0:96cc3511f894 C +C
+  
+  $ cd ..
+
+Rebase one parent with successor in destination, the other parent moves as "-d"
+requests. These two tests cover the case when the second merge base candidate
+gets selected, new parents get updated accordingly so new p1 matches the merge
+base.
+
+  $ hg init p1-succ-p2-move
+  $ cd p1-succ-p2-move
+  $ hg debugdrawdag <<'EOS'
+  >   D Z
+  >  /| | # replace: A -> C
+  > A B C # D/D = D
+  > EOS
+  $ hg rebase -r A+B+D -d Z --config experimental.rebaseskipobsolete=0
+  rebasing 0:426bada5c675 "A" (A)
+  rebasing 1:fc2b737bb2e5 "B" (B)
+  rebasing 3:b8ed089c80ad "D" (D)
+
+  $ rm .hg/localtags
+  $ hg log -G
+  o    7:7636985f7fde D
+  |\
+  | o  6:76840d832e98 B
+  | |
+  o |  5:a81a74d764a6 A
+  |/
+  o  4:50e41c1f3950 Z
+  |
+  o  2:96cc3511f894 C
+  
+  $ hg files -r tip
+  A
+  B
+  C
+  D
+  Z
+
+  $ cd ..
+
+With p1 and p2 swapped from the above case
+
+  $ hg init p1-move-p2-succ
+  $ cd p1-move-p2-succ
+  $ hg debugdrawdag <<'EOS'
+  >   D Z
+  >  /| |  # replace: B -> C
+  > A B C  # D/D = D
+  > EOS
+  $ hg rebase -r B+A+D -d Z --config experimental.rebaseskipobsolete=0
+  rebasing 0:426bada5c675 "A" (A)
+  rebasing 1:fc2b737bb2e5 "B" (B)
+  rebasing 3:b8ed089c80ad "D" (D)
+
+  $ rm .hg/localtags
+  $ hg log -G
+  o    7:7636985f7fde D
+  |\
+  | o  6:76840d832e98 B
+  | |
+  o |  5:a81a74d764a6 A
+  |/
+  o  4:50e41c1f3950 Z
+  |
+  o  2:96cc3511f894 C
+  
+  $ hg files -r tip
+  A
+  B
+  C
+  D
+  Z
+
+  $ cd ..
+
 Test that bookmark is moved and working dir is updated when all changesets have
 equivalents in destination
   $ hg init rbsrepo && cd rbsrepo