diff --git a/remote.go b/remote.go
index 2409301..c07c5af 100644
--- a/remote.go
+++ b/remote.go
@@ -92,9 +92,14 @@
 	}
 
 	isDelete := false
+	allDelete := true
 	for _, rs := range o.RefSpecs {
 		if rs.IsDelete() {
 			isDelete = true
+		} else {
+			allDelete = false
+		}
+		if isDelete && !allDelete {
 			break
 		}
 	}
@@ -132,9 +137,13 @@
 	// we are aware.
 	haves = append(haves, stop...)
 
-	hashesToPush, err := revlist.Objects(r.s, objects, haves)
-	if err != nil {
-		return err
+	var hashesToPush []plumbing.Hash
+	// Avoid the expensive revlist operation if we're only doing deletes.
+	if !allDelete {
+		hashesToPush, err = revlist.Objects(r.s, objects, haves)
+		if err != nil {
+			return err
+		}
 	}
 
 	rs, err := pushHashes(ctx, s, r.s, req, hashesToPush)
diff --git a/remote_test.go b/remote_test.go
index e2fd8ae..51180ce 100644
--- a/remote_test.go
+++ b/remote_test.go
@@ -538,6 +538,42 @@
 	})
 }
 
+func (s *RemoteSuite) TestPushNewReferenceAndDeleteInBatch(c *C) {
+	fs := fixtures.Basic().One().DotGit()
+	url := c.MkDir()
+	server, err := PlainClone(url, true, &CloneOptions{
+		URL: fs.Root(),
+	})
+
+	r, err := PlainClone(c.MkDir(), true, &CloneOptions{
+		URL: url,
+	})
+	c.Assert(err, IsNil)
+
+	remote, err := r.Remote(DefaultRemoteName)
+	c.Assert(err, IsNil)
+
+	ref, err := r.Reference(plumbing.ReferenceName("refs/heads/master"), true)
+	c.Assert(err, IsNil)
+
+	err = remote.Push(&PushOptions{RefSpecs: []config.RefSpec{
+		"refs/heads/master:refs/heads/branch2",
+		":refs/heads/branch",
+	}})
+	c.Assert(err, IsNil)
+
+	AssertReferences(c, server, map[string]string{
+		"refs/heads/branch2": ref.Hash().String(),
+	})
+
+	AssertReferences(c, r, map[string]string{
+		"refs/remotes/origin/branch2": ref.Hash().String(),
+	})
+
+	_, err = server.Storer.Reference(plumbing.ReferenceName("refs/heads/branch"))
+	c.Assert(err, Equals, plumbing.ErrReferenceNotFound)
+}
+
 func (s *RemoteSuite) TestPushInvalidEndpoint(c *C) {
 	r := newRemote(nil, &config.RemoteConfig{Name: "foo", URLs: []string{"http://\\"}})
 	err := r.Push(&PushOptions{RemoteName: "foo"})