--- a/push_cmd.py
+++ b/push_cmd.py
@@ -68,24 +68,60 @@ def push_revisions_to_subversion(ui, rep
     merc_util._encoding = oldencoding
     return 0
 
+def _getdirchanges(svn, branchpath, parentctx, ctx, changedfiles):
+    """Compute directories to add or delete when moving from parentctx
+    to ctx, assuming only 'changedfiles' files changed.
 
-def _findmissing(dirname, svn, branch_path):
-    """Find missing directories in svn. dirname *must* end in a /
+    Return (added, deleted) where 'added' is the list of all added
+    directories and 'deleted' the list of deleted directories.
+    Intermediate directories are included: if a/b/c is new and requires
+    the addition of a/b and a, those will be listed too. Intermediate
+    deleted directories are also listed, but item order of undefined
+    in either list.
     """
-    assert dirname[-1] == '/'
-    missing = []
-    keep_checking = True
-    # check and see if the dir exists svn-side.
-    path = dirname
-    while keep_checking:
+    def exists(svndir):
         try:
-            assert svn.list_dir('%s/%s' % (branch_path, path))
-            keep_checking = False
-        except core.SubversionException, e:
-            # dir must not exist
-            missing.append(path[:-1])
-            path = '/'.join(path.split('/')[:-2] + [''])
-    return missing
+            svn.list_dir('%s/%s' % (branchpath, svndir))
+            return True
+        except core.SubversionException:
+            return False
+
+    def finddirs(path):
+        pos = path.rfind('/')
+        while pos != -1:
+            yield path[:pos]
+            pos = path.rfind('/', 0, pos)
+
+    def getctxdirs(ctx, keptdirs):
+        dirs = {}
+        for f in ctx.manifest():
+            for d in finddirs(f):
+                if d in dirs:
+                    break
+                if d in keptdirs:
+                    dirs[d] = 1
+        return dirs
+
+    deleted, added = [], []
+    if not changedfiles:
+        return added, deleted
+    changeddirs = {}
+    for f in changedfiles:
+        for d in finddirs(f):
+            changeddirs[d] = 1
+    olddirs = getctxdirs(parentctx, changeddirs)
+    newdirs = getctxdirs(ctx, changeddirs)
+
+    for d in newdirs:
+        if d not in olddirs and not exists(d):
+            added.append(d)
+
+    for d in olddirs:
+        if d not in newdirs and exists(d):
+            deleted.append(d)
+
+    return added, deleted
+        
 
 def commit_from_rev(ui, repo, rev_ctx, hg_editor, svn_url, base_revision):
     """Build and send a commit from Mercurial to Subversion.
@@ -99,7 +135,10 @@ def commit_from_rev(ui, repo, rev_ctx, h
     if parent_branch and parent_branch != 'default':
         branch_path = 'branches/%s' % parent_branch
 
-    added_dirs = []
+    addeddirs, deleteddirs = _getdirchanges(svn, branch_path, parent, 
+                                            rev_ctx, rev_ctx.files())
+    deleteddirs = set(deleteddirs)
+
     props = {}
     copies = {}
     for file in rev_ctx.files():
@@ -124,9 +163,6 @@ def commit_from_rev(ui, repo, rev_ctx, h
 
                 action = 'add'
                 dirname = '/'.join(file.split('/')[:-1] + [''])
-                # check for new directories
-                if not list(parent.walk(util.PrefixMatch(dirname))):
-                    added_dirs += _findmissing(dirname, svn, branch_path)
             else:
                 base_data = parent.filectx(file).data()
                 if ('x' in parent.filectx(file).flags()
@@ -137,11 +173,25 @@ def commit_from_rev(ui, repo, rev_ctx, h
                     props.setdefault(file, {})['svn:special'] = None
                 action = 'modify'
         else:
+            pos = file.rfind('/')
+            if pos >= 0:
+                if file[:pos] in deleteddirs:
+                    # This file will be removed when its directory is removed
+                    continue
             base_data = parent.filectx(file).data()
             action = 'delete'
         file_data[file] = base_data, new_data, action
 
-    # TODO check for directory deletes here
+    # Now we are done with files, we can prune deleted directories
+    # against themselves: ignore a/b if a/ is already removed
+    deleteddirs2 = list(deleteddirs)
+    deleteddirs2.sort()
+    deleteddirs2.reverse()
+    for d in deleteddirs2:
+        pos = d.rfind('/')
+        if pos >= 0 and d[:pos] in deleteddirs:
+            deleteddirs.remove(d[:pos])
+
     def svnpath(p):
         return '%s/%s' % (branch_path, p)
 
@@ -149,8 +199,8 @@ def commit_from_rev(ui, repo, rev_ctx, h
     for source, dest in copies.iteritems():
         newcopies[svnpath(source)] = (svnpath(dest), base_revision)
 
-    new_target_files = [svnpath(f) for f in rev_ctx.files()]
-    for tf, ntf in zip(rev_ctx.files(), new_target_files):
+    new_target_files = [svnpath(f) for f in file_data]
+    for tf, ntf in zip(file_data, new_target_files):
         if tf in file_data:
             file_data[ntf] = file_data[tf]
             if tf in props:
@@ -160,12 +210,14 @@ def commit_from_rev(ui, repo, rev_ctx, h
                 props.setdefault(ntf, {}).update(props.get(ntf, {}))
                 props.setdefault(ntf, {})['svn:mime-type'] = 'application/octet-stream'
             del file_data[tf]
-    added_dirs = ['%s/%s' % (branch_path, f) for f in added_dirs]
-    added_dirs = set(added_dirs)
-    new_target_files += added_dirs
+
+    addeddirs = [svnpath(d) for d in addeddirs]
+    deleteddirs = [svnpath(d) for d in deleteddirs]
+    new_target_files += addeddirs + deleteddirs
     try:
         svn.commit(new_target_files, rev_ctx.description(), file_data,
-                   base_revision, set(added_dirs), props, newcopies)
+                   base_revision, set(addeddirs), set(deleteddirs), 
+                   props, newcopies)
     except core.SubversionException, e:
         if hasattr(e, 'apr_err') and e.apr_err == 160028:
             raise merc_util.Abort('Base text was out of date, maybe rebase?')

--- a/svnwrap/svn_swig_wrapper.py
+++ b/svnwrap/svn_swig_wrapper.py
@@ -269,8 +269,8 @@ class SubversionRepo(object):
                 yield revisions[0]
                 revisions.pop(0)
 
-    def commit(self, paths, message, file_data, base_revision, dirs,
-               properties, copies):
+    def commit(self, paths, message, file_data, base_revision, addeddirs,
+               deleteddirs, properties, copies):
         """Commits the appropriate targets from revision in editor's store.
         """
         self.init_ra_and_client()
@@ -292,10 +292,14 @@ class SubversionRepo(object):
                 bat = editor.open_root(edit_baton, base_revision, self.pool)
                 batons.append(bat)
                 return bat
-            if path in dirs:
+            if path in addeddirs:
                 bat = editor.add_directory(path, parent, None, -1, pool)
                 batons.append(bat)
                 return bat
+            if path in deleteddirs:
+                bat = editor.delete_entry(path, base_revision, parent, pool)
+                batons.append(bat)
+                return bat
             base_text, new_text, action = file_data[path]
             compute_delta = True
             if action == 'modify':

new file mode 100755
--- /dev/null
+++ b/tests/fixtures/emptyrepo.sh
@@ -0,0 +1,30 @@
+#!/bin/sh
+#
+# Generate renames.svndump
+#
+
+mkdir temp
+cd temp
+
+mkdir project-orig
+cd project-orig
+mkdir trunk
+mkdir branches
+cd ..
+
+svnadmin create testrepo
+svnurl=file://`pwd`/testrepo
+svn import project-orig $svnurl -m "init project"
+
+svn co $svnurl project
+cd project/trunk
+# Create and remove a file, hgsubversion does not like
+# empty repositories
+echo a > a
+svn add a
+svn ci -m "add a"
+svn rm a
+svn ci -m "remove a"
+cd ../..
+
+svnadmin dump testrepo > ../emptyrepo.svndump

new file mode 100644
--- /dev/null
+++ b/tests/fixtures/emptyrepo.svndump
@@ -0,0 +1,102 @@
+SVN-fs-dump-format-version: 2
+
+UUID: d3a5b63a-6d97-4aaf-9707-be98248d5c9e
+
+Revision-number: 0
+Prop-content-length: 56
+Content-length: 56
+
+K 8
+svn:date
+V 27
+2008-11-10T14:47:35.612188Z
+PROPS-END
+
+Revision-number: 1
+Prop-content-length: 114
+Content-length: 114
+
+K 7
+svn:log
+V 12
+init project
+K 10
+svn:author
+V 7
+pmezard
+K 8
+svn:date
+V 27
+2008-11-10T14:47:35.655615Z
+PROPS-END
+
+Node-path: branches
+Node-kind: dir
+Node-action: add
+Prop-content-length: 10
+Content-length: 10
+
+PROPS-END
+
+
+Node-path: trunk
+Node-kind: dir
+Node-action: add
+Prop-content-length: 10
+Content-length: 10
+
+PROPS-END
+
+
+Revision-number: 2
+Prop-content-length: 106
+Content-length: 106
+
+K 7
+svn:log
+V 5
+add a
+K 10
+svn:author
+V 7
+pmezard
+K 8
+svn:date
+V 27
+2008-11-10T14:47:36.172222Z
+PROPS-END
+
+Node-path: trunk/a
+Node-kind: file
+Node-action: add
+Prop-content-length: 10
+Text-content-length: 2
+Text-content-md5: 60b725f10c9c85c70d97880dfe8191b3
+Content-length: 12
+
+PROPS-END
+a
+
+
+Revision-number: 3
+Prop-content-length: 109
+Content-length: 109
+
+K 7
+svn:log
+V 8
+remove a
+K 10
+svn:author
+V 7
+pmezard
+K 8
+svn:date
+V 27
+2008-11-10T14:47:37.171799Z
+PROPS-END
+
+Node-path: trunk/a
+Node-action: delete
+
+

--- a/tests/run.py
+++ b/tests/run.py
@@ -8,6 +8,8 @@ import test_fetch_command
 import test_fetch_command_regexes
 import test_fetch_renames
 import test_push_command
+import test_push_renames
+import test_push_dirs
 import test_tags
 
 def suite():
@@ -15,6 +17,8 @@ def suite():
                                test_fetch_command_regexes.suite(),
                                test_fetch_renames.suite(),
                                test_push_command.suite(),
+                               test_push_renames.suite(),
+                               test_push_dirs.suite(),
                                test_tags.suite(),
                               ])
 

--- a/tests/test_push_command.py
+++ b/tests/test_push_command.py
@@ -266,59 +266,6 @@ class PushTests(test_util.TestBase):
         self.assertEqual([x for x in tip.manifest().keys() if 'l' not in
                           tip[x].flags()], ['alpha', 'beta', 'adding_file', ])
 
-    def test_push_with_new_dir(self):
-        self.test_push_to_default(commit=True)
-        repo = self.repo
-        def file_callback(repo, memctx, path):
-            if path == 'newdir/gamma':
-                return context.memfilectx(path=path,
-                                          data='foo',
-                                          islink=False,
-                                          isexec=False,
-                                          copied=False)
-            raise IOError()
-        ctx = context.memctx(repo,
-                             (repo['tip'].node(), node.nullid),
-                             'message',
-                             ['newdir/gamma', ],
-                             file_callback,
-                             'author',
-                             '2008-10-29 21:26:00 -0500',
-                             {'branch': 'default', })
-        new_hash = repo.commitctx(ctx)
-        hg.update(repo, repo['tip'].node())
-        self.pushrevisions()
-        tip = self.repo['tip']
-        self.assertNotEqual(tip.node(), new_hash)
-        self.assertEqual(tip['newdir/gamma'].data(), 'foo')
-
-    def test_push_with_new_subdir(self):
-        self.test_push_to_default(commit=True)
-        repo = self.repo
-        def file_callback(repo, memctx, path):
-            if path == 'newdir/subdir/gamma':
-                return context.memfilectx(path=path,
-                                          data='foo',
-                                          islink=False,
-                                          isexec=False,
-                                          copied=False)
-            raise IOError()
-        ctx = context.memctx(repo,
-                             (repo['tip'].node(), node.nullid),
-                             'message',
-                             ['newdir/subdir/gamma', ],
-                             file_callback,
-                             'author',
-                             '2008-10-29 21:26:00 -0500',
-                             {'branch': 'default', })
-        new_hash = repo.commitctx(ctx)
-        hg.update(repo, repo['tip'].node())
-        self.pushrevisions()
-        tip = self.repo['tip']
-        self.assertNotEqual(tip.node(), new_hash)
-        self.assertEqual(tip['newdir/subdir/gamma'].data(), 'foo')
-
-
     def test_push_existing_file_newly_symlink(self):
         self.test_push_existing_file_newly_execute(execute=False,
                                                    link=True,

new file mode 100644
--- /dev/null
+++ b/tests/test_push_dirs.py
@@ -0,0 +1,90 @@
+import os
+import sys
+import unittest
+
+from mercurial import context
+from mercurial import hg
+from mercurial import node
+
+import test_util
+
+class TestPushDirectories(test_util.TestBase):
+    def setUp(self):
+        test_util.TestBase.setUp(self)
+        test_util.load_fixture_and_fetch('emptyrepo.svndump',
+                                         self.repo_path,
+                                         self.wc_path)
+
+    def _commitchanges(self, repo, changes):
+        parentctx = repo['tip']
+
+        changed, removed = [], []
+        for source, dest, newdata in changes:
+            if dest is None:
+                removed.append(source)
+            else:
+                changed.append(dest)
+
+        def filectxfn(repo, memctx, path):
+            if path in removed:
+                raise IOError()
+            entry = [e for e in changes if path == e[1]][0]
+            source, dest, newdata = entry
+            if newdata is None:
+                newdata = parentctx[source].data()
+            copied = None
+            if source != dest:
+                copied = source
+            return context.memfilectx(path=dest,
+                                      data=newdata,
+                                      islink=False,
+                                      isexec=False,
+                                      copied=copied)
+        
+        ctx = context.memctx(repo,
+                             (parentctx.node(), node.nullid),
+                             'automated test',
+                             changed + removed,
+                             filectxfn,
+                             'an_author',
+                             '2008-10-07 20:59:48 -0500')
+        nodeid = repo.commitctx(ctx)
+        repo = self.repo
+        hg.update(repo, nodeid)
+        return nodeid
+
+    def test_push_dirs(self, commit=True):
+        changes = [
+            # Single file in single directory
+            ('d1/a', 'd1/a', 'a\n'),
+            # Two files in one directory
+            ('d2/a', 'd2/a', 'a\n'),
+            ('d2/b', 'd2/b', 'a\n'),
+            # Single file in empty directory hierarchy
+            ('d31/d32/d33/d34/a', 'd31/d32/d33/d34/a', 'a\n'),
+            ('d31/d32/a', 'd31/d32/a', 'a\n'),
+            ]
+        self._commitchanges(self.repo, changes)
+        self.pushrevisions()
+        self.assertEqual(self.svnls('trunk'), 
+                          ['d1', 'd1/a', 'd2', 'd2/a', 'd2/b', 'd31', 
+                           'd31/d32', 'd31/d32/a', 'd31/d32/d33', 
+                           'd31/d32/d33/d34', 'd31/d32/d33/d34/a'])
+
+        changes = [
+            # Remove single file in single directory
+            ('d1/a', None, None),
+            # Remove one file out of two
+            ('d2/a', None, None),
+            # Removing this file should remove one empty parent dir too
+            ('d31/d32/d33/d34/a', None, None),
+            ]
+        self._commitchanges(self.repo, changes)
+        self.pushrevisions()
+        self.assertEqual(self.svnls('trunk'), 
+                         ['d2', 'd2/b', 'd31', 'd31/d32', 'd31/d32/a', 'd31/d32/d33'])
+
+def suite():
+    all = [unittest.TestLoader().loadTestsFromTestCase(TestPushDirectories),
+          ]
+    return unittest.TestSuite(all)

--- a/tests/test_util.py
+++ b/tests/test_util.py
@@ -71,7 +71,7 @@ class TestBase(unittest.TestCase):
     def tearDown(self):
         rmtree(self.tmpdir)
         os.chdir(self.oldwd)
-
+        
     # define this as a property so that it reloads anytime we need it
     @property
     def repo(self):
@@ -81,3 +81,17 @@ class TestBase(unittest.TestCase):
         push_cmd.push_revisions_to_subversion(
             ui.ui(), repo=self.repo, hg_repo_path=self.wc_path,
             svn_url=fileurl(self.repo_path))
+
+    def svnls(self, path, rev='HEAD'):
+        path = self.repo_path + '/' + path
+        path = fileurl(path)
+        args = ['svn', 'ls', '-r', rev, '-R', path]
+        p = subprocess.Popen(args, 
+                             stdout=subprocess.PIPE, 
+                             stderr=subprocess.PIPE)
+        stdout, stderr = p.communicate()
+        if p.returncode:
+            raise Exception('svn ls failed on %s: %r' % (path, stderr))
+        entries = [e.strip('/') for e in stdout.splitlines()]
+        entries.sort()
+        return entries