diff --git a/gnu/services.scm b/gnu/services.scm
index 9f6e323e1..500724eec 100644
--- a/gnu/services.scm
+++ b/gnu/services.scm
@@ -248,9 +248,9 @@ directory."
   ;; The service that produces the boot script.
   (service boot-service-type #t))
 
-(define (cleanup-gexp _)
+(define (cleanup-gexp locale)
   "Return as a monadic value a gexp to clean up /tmp and similar places upon
-boot."
+boot.  Run with LOCALE to ensure file names are properly decoded."
   (with-monad %store-monad
     (with-imported-modules '((guix build utils))
       (return #~(begin
@@ -272,6 +272,13 @@ boot."
                                                 #t))))
                     ;; Ignore I/O errors so the system can boot.
                     (fail-safe
+                     ;; Guile decodes file names according to the current
+                     ;; locale's encoding so attempt to use an appropriate
+                     ;; locale.  See <https://bugs.gnu.org/26353>.
+                     ;; TODO: With Guile 2.2, choose an ISO-8859-1 locale
+                     ;; to disable decoding altogether.
+                     (setlocale LC_CTYPE #$locale)
+
                      (delete-file-recursively "/tmp")
                      (delete-file-recursively "/var/run")
                      (mkdir "/tmp")
@@ -280,7 +287,8 @@ boot."
                      (chmod "/var/run" #o755))))))))
 
 (define cleanup-service-type
-  ;; Service that cleans things up in /tmp and similar.
+  ;; Service that cleans things up in /tmp and similar.  Its value is the name
+  ;; of a locale to install before traversing these directories.
   (service-type (name 'cleanup)
                 (extensions
                  (list (service-extension boot-service-type
diff --git a/gnu/system.scm b/gnu/system.scm
index 0f52351cf..5e0d2db7d 100644
--- a/gnu/system.scm
+++ b/gnu/system.scm
@@ -309,7 +309,8 @@ a container or that of a \"bare metal\" system."
            ;; activation code.
            %shepherd-root-service
            %activation-service
-           (service cleanup-service-type #f)
+           (service cleanup-service-type
+                    (operating-system-locale os))
 
            (pam-root-service (operating-system-pam-services os))
            (account-service (append (operating-system-accounts os)