diff --git a/gnu/local.mk b/gnu/local.mk
index f2b480bded..7056d4fdbc 100644
--- a/gnu/local.mk
+++ b/gnu/local.mk
@@ -1804,7 +1804,6 @@ 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-program-lookup.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 992ef82d3f..abd403af34 100644
--- a/gnu/packages/containers.scm
+++ b/gnu/packages/containers.scm
@@ -44,10 +44,13 @@ (define-module (gnu packages containers)
   #:use-module (gnu packages check)
   #:use-module (gnu packages compression)
   #:use-module (gnu packages glib)
+  #:use-module (gnu packages gcc)
   #:use-module (gnu packages gnupg)
   #:use-module (gnu packages golang)
   #:use-module (gnu packages guile)
   #:use-module (gnu packages linux)
+  #:use-module (gnu packages man)
+  #:use-module (gnu packages pcre)
   #:use-module (gnu packages python)
   #:use-module (gnu packages networking)
   #:use-module (gnu packages pkg-config)
@@ -449,84 +452,104 @@ (define-public podman
        (uri (git-reference
              (url "https://github.com/containers/podman")
              (commit (string-append "v" version))))
-       (modules '((guix build utils)))
-       ;; FIXME: Btrfs libraries not detected by these scripts.
-       (snippet '(substitute* "Makefile"
-                   ((".*hack/btrfs.*") "")))
-       (patches
-        (search-patches
-         "podman-program-lookup.patch"))
        (sha256
         (base32 "0g15m10mgwssw5axkyn2ms5k858dbc6vf3cbxv7hvdncgwnfk5f0"))
        (file-name (git-file-name name version))))
-
     (build-system gnu-build-system)
     (arguments
      (list
       #:make-flags
-      #~(list #$(string-append "CC=" (cc-for-target))
-              (string-append "PREFIX=" #$output))
+      #~(list (string-append "CC=" #$(cc-for-target))
+              (string-append "PREFIX=" #$output)
+              (string-append "HELPER_BINARIES_DIR=" #$output "/_guix")
+              (string-append "GOMD2MAN="
+                             #$go-github-com-go-md2man "/bin/go-md2man"))
       #:tests? #f                  ; /sys/fs/cgroup not set up in guix sandbox
       #:test-target "test"
+      #:imported-modules
+      (source-module-closure `(,@%gnu-build-system-modules
+                               (guix build go-build-system)))
       #:phases
       #~(modify-phases %standard-phases
           (delete 'configure)
           (add-after 'unpack 'set-env
-            (lambda* (#:key inputs #:allow-other-keys)
-              ;; when running go, things fail because
-              ;; HOME=/homeless-shelter.
-              (setenv "HOME" "/tmp")))
+            (lambda _
+              ;; When running go, things fail because HOME=/homeless-shelter.
+              (setenv "HOME" "/tmp")
+              ;; Required for detecting btrfs in hack/btrfs* due to bug in GNU
+              ;; Make <4.4 causing CC not to be propagated into $(shell ...)
+              ;; calls.  Can be removed once we update to >4.3.
+              (setenv "CC" #$(cc-for-target))))
           (replace 'check
             (lambda* (#:key tests? #:allow-other-keys)
               (when tests?
-                ;; (invoke "strace" "-f" "bin/podman" "version")
                 (invoke "make" "localsystem")
                 (invoke "make" "remotesystem"))))
           (add-after 'unpack 'fix-hardcoded-paths
             (lambda _
-              (substitute* "vendor/github.com/containers/common/pkg/config/config.go"
-                (("@SLIRP4NETNS_DIR@")
-                 (string-append #$slirp4netns "/bin"))
-                (("@PASST_DIR@")
-                 (string-append #$passt "/bin"))
-                (("@NETAVARK_DIR@")
-                 (string-append #$netavark "/bin")))
-              (substitute* "hack/install_catatonit.sh"
-                (("CATATONIT_PATH=\"[^\"]+\"")
-                 (string-append "CATATONIT_PATH=" (which "true"))))
               (substitute* "vendor/github.com/containers/common/pkg/config/config_linux.go"
                 (("/usr/local/libexec/podman")
                  (string-append #$output "/libexec/podman"))
                 (("/usr/local/lib/podman")
-                 (string-append #$output "/bin")))
-              (substitute* "vendor/github.com/containers/common/pkg/config/default.go"
-                (("/usr/libexec/podman/conmon") (which "conmon"))
-                (("/usr/local/libexec/cni")
-                 (string-append #$(this-package-input "cni-plugins")
-                                "/bin"))
-                (("/usr/bin/crun") (which "crun")))))
+                 (string-append #$output "/bin")))))
+          (add-after 'install 'symlink-helpers
+            (lambda _
+              (mkdir-p (string-append #$output "/_guix"))
+              (for-each
+               (lambda (what)
+                 (symlink (string-append (car what) "/bin/" (cdr what))
+                          (string-append #$output "/_guix/" (cdr what))))
+               ;; Only tools that cannot be discovered via $PATH are
+               ;; symlinked.  Rest is handled in the 'wrap-podman phase.
+               `((#$aardvark-dns     . "aardvark-dns")
+                 ;; Required for podman-machine, which is *not* supported out
+                 ;; of the box.  But it cannot be discovered via $PATH, so
+                 ;; there is no other way for the user to install it.  It
+                 ;; costs ~10MB, so let's leave it here.
+                 (#$gvisor-tap-vsock . "gvproxy")
+                 (#$netavark         . "netavark")))))
+          (add-after 'install 'wrap-podman
+            (lambda _
+              (wrap-program (string-append #$output "/bin/podman")
+                `("PATH" suffix
+                  (,(string-append #$catatonit      "/bin")
+                   ,(string-append #$conmon         "/bin")
+                   ,(string-append #$crun           "/bin")
+                   ,(string-append #$gcc            "/bin") ; cpp
+                   ,(string-append #$iptables       "/sbin")
+                   ,(string-append #$passt          "/bin")
+                   ,(string-append #$procps         "/bin") ; ps
+                   "/run/setuid-programs")))))
+          (add-after 'install 'remove-go-references
+            (lambda* (#:key inputs #:allow-other-keys)
+              (let ((go (assoc-ref inputs "go")))
+                (for-each
+                 (lambda (file)
+                   (when (executable-file? file)
+                     ((@@ (guix build go-build-system) remove-store-reference)
+                      file go)))
+                 (append (find-files (string-append #$output "/bin"))
+                         (find-files (string-append #$output "/libexec"))
+                         (find-files (string-append #$output "/lib")))))))
           (add-after 'install 'install-completions
             (lambda _
               (invoke "make" "install.completions"
                       (string-append "PREFIX=" #$output)))))))
     (inputs
-     (list btrfs-progs
-           cni-plugins
-           conmon
-           crun
+     (list bash-minimal
+           btrfs-progs
            gpgme
-           go-github-com-go-md2man
-           iptables
            libassuan
            libseccomp
-           libselinux
-           passt
-           slirp4netns))
+           libselinux))
     (native-inputs
-     (list bats
+     (list (package/inherit grep
+             (inputs (list pcre2)))     ; Drop once grep on master supports -P
+           bats
            git
            go-1.21
-           ; strace ; XXX debug
+           go-github-com-go-md2man
+           mandoc
            pkg-config
            python))
     (home-page "https://podman.io")
@@ -536,8 +559,14 @@ (define-public podman
 volumes mounted into those containers, and pods made from groups of
 containers.
 
-The @code{machine} subcommand is not supported due to gvproxy not being
-packaged.")
+Not all commands are working out of the box due to requiring additional
+binaries to be present in the $PATH.
+
+To get @code{podman compose} working, install either @code{podman-compose} or
+@code{docker-compose} packages.
+
+To get @code{podman machine} working, install @code{qemu-minimal}, and
+@code{openssh} packages.")
     (license license:asl2.0)))
 
 (define-public podman-compose
diff --git a/gnu/packages/patches/podman-program-lookup.patch b/gnu/packages/patches/podman-program-lookup.patch
deleted file mode 100644
index 27a9421285..0000000000
--- a/gnu/packages/patches/podman-program-lookup.patch
+++ /dev/null
@@ -1,120 +0,0 @@
-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
-
