diff --git a/internal/config/nsmgr/types_linux.go b/internal/config/nsmgr/types_linux.go
index 38b30ee8a0e..9a0d538778d 100644
--- a/internal/config/nsmgr/types_linux.go
+++ b/internal/config/nsmgr/types_linux.go
@@ -83,11 +83,17 @@ func (n *namespace) Remove() error {
 		return nil
 	}
 
-	// try to unmount, ignoring "not mounted" (EINVAL) error.
-	if err := unix.Unmount(fp, unix.MNT_DETACH); err != nil && err != unix.EINVAL {
-		return fmt.Errorf("unable to unmount %s: %w", fp, err)
+	// Don't run into unmount issues if the network namespace does not exist any more.
+	if _, err := os.Stat(fp); err == nil {
+		// try to unmount, ignoring "not mounted" (EINVAL) error.
+		if err := unix.Unmount(fp, unix.MNT_DETACH); err != nil && err != unix.EINVAL {
+			return fmt.Errorf("unable to unmount %s: %w", fp, err)
+		}
+
+		return os.RemoveAll(fp)
 	}
-	return os.Remove(fp)
+
+	return nil
 }
 
 // GetNamespace takes a path and type, checks if it is a namespace, and if so
diff --git a/server/sandbox_network.go b/server/sandbox_network.go
index d8b8efc1548..86ddf475ce4 100644
--- a/server/sandbox_network.go
+++ b/server/sandbox_network.go
@@ -4,6 +4,7 @@ import (
 	"context"
 	"fmt"
 	"math"
+	"os"
 	"time"
 
 	cnitypes "github.com/containernetworking/cni/pkg/types"
@@ -187,7 +188,19 @@ func (s *Server) networkStop(ctx context.Context, sb *sandbox.Sandbox) error {
 		return err
 	}
 	if err := s.config.CNIPlugin().TearDownPodWithContext(stopCtx, podNetwork); err != nil {
-		return fmt.Errorf("failed to destroy network for pod sandbox %s(%s): %w", sb.Name(), sb.ID(), err)
+		retErr := fmt.Errorf("failed to destroy network for pod sandbox %s(%s): %w", sb.Name(), sb.ID(), err)
+
+		if _, statErr := os.Stat(podNetwork.NetNS); statErr != nil {
+			return fmt.Errorf("%w: stat netns path %q: %w", retErr, podNetwork.NetNS, statErr)
+		}
+
+		// The netns file may still exists, which means that it's likely
+		// corrupted. Remove it to allow cleanup of the network namespace:
+		if rmErr := os.RemoveAll(podNetwork.NetNS); rmErr != nil {
+			return fmt.Errorf("%w: failed to remove netns path: %w", retErr, rmErr)
+		}
+
+		log.Warnf(ctx, "Removed invalid netns path %s from pod sandbox %s(%s)", podNetwork.NetNS, sb.Name(), sb.ID())
 	}
 
 	return sb.SetNetworkStopped(ctx, true)
diff --git a/test/network.bats b/test/network.bats
index 2d26beda62f..2c89725c66a 100644
--- a/test/network.bats
+++ b/test/network.bats
@@ -166,3 +166,24 @@ function check_networking() {
 	# shellcheck disable=SC2010
 	[[ $(ls $CNI_RESULTS_DIR | grep "$POD") == "" ]]
 }
+
+@test "Clean up network if pod netns gets destroyed" {
+	start_crio
+
+	POD=$(crictl runp "$TESTDATA/sandbox_config.json")
+
+	# remove the network namespace
+	NETNS_PATH=/var/run/netns/
+	NS=$(crictl inspectp "$POD" |
+		jq -er '.info.runtimeSpec.linux.namespaces[] | select(.type == "network").path | sub("'$NETNS_PATH'"; "")')
+
+	# remove network namespace
+	ip netns del "$NS"
+
+	# fake invalid netns path
+	touch "$NETNS_PATH$NS"
+
+	# be able to remove the sandbox
+	crictl rmp -f "$POD"
+	grep -q "Removed invalid netns path $NETNS_PATH$NS from pod sandbox" "$CRIO_LOG"
+}