diff --git a/gnu/local.mk b/gnu/local.mk
index becca7dd56..ddc14acb9c 100644
--- a/gnu/local.mk
+++ b/gnu/local.mk
@@ -1786,6 +1786,7 @@ dist_patch_DATA =						\
   %D%/packages/patches/plasp-fix-normalization.patch \
   %D%/packages/patches/plasp-include-iostream.patch \
   %D%/packages/patches/pocketfft-cpp-prefer-preprocessor-if.patch			\
+  %D%/packages/patches/podman-Modify-search-for-binaries-to-fit-Guix-model.patch \
   %D%/packages/patches/pokerth-boost.patch			\
   %D%/packages/patches/ppsspp-disable-upgrade-and-gold.patch		\
   %D%/packages/patches/procps-strtod-test.patch                 \
diff --git a/gnu/packages/containers.scm b/gnu/packages/containers.scm
index 5b79e8a446..b16ea26341 100644
--- a/gnu/packages/containers.scm
+++ b/gnu/packages/containers.scm
@@ -342,7 +342,7 @@ (define-public cni-plugins
 (define-public podman
   (package
     (name "podman")
-    (version "4.4.1")
+    (version "4.9.3")
     (source
      (origin
        (method git-fetch)
@@ -353,8 +353,11 @@ (define-public podman
        ;; FIXME: Btrfs libraries not detected by these scripts.
        (snippet '(substitute* "Makefile"
                    ((".*hack/btrfs.*") "")))
+       (patches
+        (search-patches
+         "podman-Modify-search-for-binaries-to-fit-Guix-model.patch"))
        (sha256
-        (base32 "0qbr6rbyig3c2hvdvmd94jjkg820hpdz6j7dgyv62dl6wfwvj5jj"))
+        (base32 "17g7n09ndxhpjr39s9qwxdcv08wavjj0g5nmnrvrkz2wgdqigl1x"))
        (file-name (git-file-name name version))))
 
     (build-system gnu-build-system)
@@ -381,10 +384,11 @@ (define-public podman
                 (invoke "make" "remotesystem"))))
           (add-after 'unpack 'fix-hardcoded-paths
             (lambda _
-              (substitute* (find-files "libpod" "\\.go")
-                (("exec.LookPath[(][\"]slirp4netns[\"][)]")
-                 (string-append "exec.LookPath(\""
-                                (which "slirp4netns") "\")")))
+              (substitute* "vendor/github.com/containers/common/pkg/config/config.go"
+                (("@SLIRP4NETNS_DIR@")
+                 (string-append #$slirp4netns "/bin"))
+                (("@PASST_DIR@")
+                 (string-append #$passt "/bin")))
               (substitute* "hack/install_catatonit.sh"
                 (("CATATONIT_PATH=\"[^\"]+\"")
                  (string-append "CATATONIT_PATH=" (which "true"))))
@@ -414,11 +418,12 @@ (define-public podman
            libassuan
            libseccomp
            libselinux
+           passt
            slirp4netns))
     (native-inputs
      (list bats
            git
-           go-1.19
+           go-1.21
            ; strace ; XXX debug
            pkg-config
            python))
@@ -427,7 +432,10 @@ (define-public podman
     (description
      "Podman (the POD MANager) is a tool for managing containers and images,
 volumes mounted into those containers, and pods made from groups of
-containers.")
+containers.
+
+The @code{machine} subcommand is not supported due to gvproxy not being
+packaged.")
     (license license:asl2.0)))
 
 (define-public buildah
diff --git a/gnu/packages/patches/podman-Modify-search-for-binaries-to-fit-Guix-model.patch b/gnu/packages/patches/podman-Modify-search-for-binaries-to-fit-Guix-model.patch
new file mode 100644
index 0000000000..27a9421285
--- /dev/null
+++ b/gnu/packages/patches/podman-Modify-search-for-binaries-to-fit-Guix-model.patch
@@ -0,0 +1,120 @@
+From 914aed3e04f71453fbdc30f4287e13ca3ce63a36 Mon Sep 17 00:00:00 2001
+From: Tomas Volf <~@wolfsden.cz>
+Date: Wed, 14 Feb 2024 20:02:03 +0100
+Subject: [PATCH] Modify search for binaries to fit Guix model
+
+Podman basically looked into the $PATH and into its libexec.  That does not fit
+Guix's model very well, to an additional option to specify additional
+directories during compilation was added.
+
+* pkg/rootless/rootless_linux.go
+(tryMappingTool): Also check /run/setuid-programs.
+* vendor/github.com/containers/common/pkg/config/config.go
+(extraGuixDir): New function.
+(FindHelperBinary): Use it.
+* vendor/github.com/containers/storage/pkg/unshare/unshare_linux.go
+(guixLookupSetuidPath): New function.
+(Start): Use it.
+---
+ pkg/rootless/rootless_linux.go                |  3 +++
+ .../containers/common/pkg/config/config.go    | 23 +++++++++++++++++++
+ .../storage/pkg/unshare/unshare_linux.go      | 14 +++++++++--
+ 3 files changed, 38 insertions(+), 2 deletions(-)
+
+diff --git a/pkg/rootless/rootless_linux.go b/pkg/rootless/rootless_linux.go
+index d303c8b..0191d90 100644
+--- a/pkg/rootless/rootless_linux.go
++++ b/pkg/rootless/rootless_linux.go
+@@ -102,6 +102,9 @@ func tryMappingTool(uid bool, pid int, hostID int, mappings []idtools.IDMap) err
+ 		idtype = "setgid"
+ 	}
+ 	path, err := exec.LookPath(tool)
++	if err != nil {
++		path, err = exec.LookPath("/run/setuid-programs/" + tool)
++	}
+ 	if err != nil {
+ 		return fmt.Errorf("command required for rootless mode with multiple IDs: %w", err)
+ 	}
+diff --git a/vendor/github.com/containers/common/pkg/config/config.go b/vendor/github.com/containers/common/pkg/config/config.go
+index 75b917f..ed2f131 100644
+--- a/vendor/github.com/containers/common/pkg/config/config.go
++++ b/vendor/github.com/containers/common/pkg/config/config.go
+@@ -1102,6 +1102,24 @@ func findBindir() string {
+ 	return bindirCached
+ }
+ 
++func extraGuixDir(bin_name string) string {
++	if (bin_name == "slirp4netns") {
++		return "@SLIRP4NETNS_DIR@";
++	} else if (bin_name == "pasta") {
++		return "@PASST_DIR@";
++	} else if (strings.HasPrefix(bin_name, "qemu-")) {
++		return "@QEMU_DIR@";
++	} else if (bin_name == "gvproxy") {
++		return "@GVPROXY_DIR@";
++	} else if (bin_name == "netavark") {
++		return "@NETAVARK_DIR@";
++	} else if (bin_name == "aardvark-dns") {
++		return "@AARDVARK_DNS_DIR@";
++	} else {
++		return "";
++	}
++}
++
+ // FindHelperBinary will search the given binary name in the configured directories.
+ // If searchPATH is set to true it will also search in $PATH.
+ func (c *Config) FindHelperBinary(name string, searchPATH bool) (string, error) {
+@@ -1109,6 +1127,11 @@ func (c *Config) FindHelperBinary(name string, searchPATH bool) (string, error)
+ 	bindirPath := ""
+ 	bindirSearched := false
+ 
++	if dir := extraGuixDir(name); dir != "" {
++		/* If there is a Guix dir, skip the PATH search. */
++		dirList = append([]string{dir}, dirList...)
++	}
++
+ 	// If set, search this directory first. This is used in testing.
+ 	if dir, found := os.LookupEnv("CONTAINERS_HELPER_BINARY_DIR"); found {
+ 		dirList = append([]string{dir}, dirList...)
+diff --git a/vendor/github.com/containers/storage/pkg/unshare/unshare_linux.go b/vendor/github.com/containers/storage/pkg/unshare/unshare_linux.go
+index a8dc1ba..0b0d755 100644
+--- a/vendor/github.com/containers/storage/pkg/unshare/unshare_linux.go
++++ b/vendor/github.com/containers/storage/pkg/unshare/unshare_linux.go
+@@ -26,6 +26,16 @@ import (
+ 	"github.com/syndtr/gocapability/capability"
+ )
+ 
++func guixLookupSetuidPath(prog string) (string, error) {
++	path, err := exec.LookPath(prog)
++	if err != nil {
++		path, err = exec.LookPath("/run/setuid-programs/" + prog)
++	}
++	return path, err
++}
++
++
++
+ // Cmd wraps an exec.Cmd created by the reexec package in unshare(), and
+ // handles setting ID maps and other related settings by triggering
+ // initialization code in the child.
+@@ -237,7 +247,7 @@ func (c *Cmd) Start() error {
+ 			gidmapSet := false
+ 			// Set the GID map.
+ 			if c.UseNewgidmap {
+-				path, err := exec.LookPath("newgidmap")
++				path, err := guixLookupSetuidPath("newgidmap")
+ 				if err != nil {
+ 					return fmt.Errorf("finding newgidmap: %w", err)
+ 				}
+@@ -297,7 +307,7 @@ func (c *Cmd) Start() error {
+ 			uidmapSet := false
+ 			// Set the UID map.
+ 			if c.UseNewuidmap {
+-				path, err := exec.LookPath("newuidmap")
++				path, err := guixLookupSetuidPath("newuidmap")
+ 				if err != nil {
+ 					return fmt.Errorf("finding newuidmap: %w", err)
+ 				}
+-- 
+2.41.0
+
