diff --git a/src/main/java/io/vertx/core/net/impl/pool/PoolWaiter.java b/src/main/java/io/vertx/core/net/impl/pool/PoolWaiter.java
--- a/src/main/java/io/vertx/core/net/impl/pool/PoolWaiter.java
+++ b/src/main/java/io/vertx/core/net/impl/pool/PoolWaiter.java
@@ -53,6 +53,7 @@ default void onConnect(PoolWaiter<C> waiter) {
   PoolWaiter<C> prev;
   PoolWaiter<C> next;
   boolean disposed;
+  boolean queued;
 
   PoolWaiter(PoolWaiter.Listener<C> listener, ContextInternal context, final int capacity, Handler<AsyncResult<Lease<C>>> handler) {
     this.listener = listener;
diff --git a/src/main/java/io/vertx/core/net/impl/pool/SimpleConnectionPool.java b/src/main/java/io/vertx/core/net/impl/pool/SimpleConnectionPool.java
--- a/src/main/java/io/vertx/core/net/impl/pool/SimpleConnectionPool.java
+++ b/src/main/java/io/vertx/core/net/impl/pool/SimpleConnectionPool.java
@@ -654,8 +654,9 @@ public void run() {
           }
         };
       }
-      if (pool.waiters.removeFirst(waiter)) {
+      if (pool.waiters.remove(waiter)) {
         cancelled = true;
+        waiter.disposed = true;
       } else if (!waiter.disposed) {
         waiter.disposed = true;
         cancelled = true;
@@ -710,8 +711,8 @@ public Recycle(Slot<C> slot) {
     @Override
     public Task execute(SimpleConnectionPool<C> pool) {
       if (!pool.closed && slot.connection != null) {
-        if (pool.waiters.size() > 0) {
-          PoolWaiter<C> waiter = pool.waiters.poll();
+        PoolWaiter<C> waiter = pool.waiters.poll();
+        if (waiter != null) {
           LeaseImpl<C> lease = new LeaseImpl<>(slot, waiter.handler);
           return new Task() {
             @Override
@@ -810,11 +811,15 @@ PoolWaiter<C> poll() {
         return null;
       }
       PoolWaiter<C> node = head.next;
-      removeFirst(node);
+      remove(node);
       return node;
     }
 
     void addLast(PoolWaiter<C> node) {
+      if (node.queued) {
+        throw new IllegalStateException();
+      }
+      node.queued = true;
       node.prev = head.prev;
       node.next = head;
       head.prev.next = node;
@@ -823,6 +828,10 @@ void addLast(PoolWaiter<C> node) {
     }
 
     void addFirst(PoolWaiter<C> node) {
+      if (node.queued) {
+        throw new IllegalStateException();
+      }
+      node.queued = true;
       node.prev = head;
       node.next = head.prev;
       head.next.prev = node;
@@ -830,12 +839,14 @@ void addFirst(PoolWaiter<C> node) {
       size++;
     }
 
-    boolean removeFirst(PoolWaiter<C> node) {
-      if (node.next == null) {
+    boolean remove(PoolWaiter<C> node) {
+      if (!node.queued) {
         return false;
       }
       node.next.prev = node.prev;
       node.prev.next = node.next;
+      node.next = node.prev = null;
+      node.queued = false;
       size--;
       return true;
     }

diff --git a/src/test/java/io/vertx/core/net/impl/pool/ConnectionPoolTest.java b/src/test/java/io/vertx/core/net/impl/pool/ConnectionPoolTest.java
--- a/src/test/java/io/vertx/core/net/impl/pool/ConnectionPoolTest.java
+++ b/src/test/java/io/vertx/core/net/impl/pool/ConnectionPoolTest.java
@@ -632,10 +632,15 @@ public void onEnqueue(PoolWaiter<Connection> waiter) {
         w.complete(waiter);
       }
     }, 0, ar -> fail());
-    w.get(10, TimeUnit.SECONDS);
-    pool.cancel(w.get(10, TimeUnit.SECONDS), onSuccess(removed -> {
-      assertTrue(removed);
-      testComplete();
+    PoolWaiter<Connection> waiter = w.get(10, TimeUnit.SECONDS);
+    pool.cancel(waiter, onSuccess(removed1 -> {
+      assertTrue(removed1);
+      assertEquals(0, pool.waiters());
+      pool.cancel(waiter, onSuccess(removed2 -> {
+        assertFalse(removed2);
+        assertEquals(0, pool.waiters());
+        testComplete();
+      }));
     }));
     await();
   }

Pool waiter list removal does not check correctly the waiter is in the list
The pool implementation checks incorrectly whether the waiter is enqueued in the list leading to an incorrect waiter list size.
