diff --git a/policycoreutils/scripts/fixfiles b/policycoreutils/scripts/fixfiles
index 6fb12e0451a9..1ff4d9bdf04e 100755
--- a/policycoreutils/scripts/fixfiles
+++ b/policycoreutils/scripts/fixfiles
@@ -109,6 +109,7 @@ fullFlag=0
 BOOTTIME=""
 VERBOSE="-p"
 FORCEFLAG=""
+THREADS=""
 RPMFILES=""
 PREFC=""
 RESTORE_MODE=""
@@ -152,7 +153,7 @@ newer() {
     shift
     LogReadOnly
     for m in `echo $FILESYSTEMSRW`; do
-	find $m -mount -newermt $DATE -print0 2>/dev/null | ${RESTORECON} ${FORCEFLAG} ${VERBOSE} $* -i -0 -f -
+	find $m -mount -newermt $DATE -print0 2>/dev/null | ${RESTORECON} ${FORCEFLAG} ${VERBOSE} ${THREADS} $* -i -0 -f -
     done;
 }
 
@@ -196,7 +197,7 @@ if [ -f ${PREFC} -a -x /usr/bin/diff ]; then
 		  esac; \
 	       fi; \
 	    done | \
-	${RESTORECON} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} $* -i -R -f -; \
+	${RESTORECON} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} ${THREADS} $* -i -R -f -; \
 	rm -f ${TEMPFILE} ${PREFCTEMPFILE}
 fi
 }
@@ -234,11 +235,11 @@ LogExcluded
 case "$RESTORE_MODE" in
     RPMFILES)
 	for i in `echo "$RPMFILES" | sed 's/,/ /g'`; do
-	    rpmlist $i | ${RESTORECON} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} $* -i -R -f -
+	    rpmlist $i | ${RESTORECON} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} ${THREADS} $* -i -R -f -
 	done
     ;;
     FILEPATH)
-	${RESTORECON} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} $* -R -- "$FILEPATH"
+	${RESTORECON} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} ${THREADS} $* -R -- "$FILEPATH"
     ;;
     *)
 	if [ -n "${FILESYSTEMSRW}" ]; then
@@ -246,7 +247,7 @@ case "$RESTORE_MODE" in
 	    echo "${OPTION}ing `echo ${FILESYSTEMSRW}`"
 
 	    if [ -z "$BIND_MOUNT_FILESYSTEMS" ]; then
-	        ${SETFILES} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} $* -q ${FC} ${FILESYSTEMSRW}
+	        ${SETFILES} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} $* -q ${THREADS} ${FC} ${FILESYSTEMSRW}
 	    else
 	        # we bind mount so we can fix the labels of files that have already been
 	        # mounted over
@@ -256,7 +257,7 @@ case "$RESTORE_MODE" in
 
 	            mkdir -p "${TMP_MOUNT}${m}" || exit 1
 	            mount --bind "${m}" "${TMP_MOUNT}${m}" || exit 1
-	            ${SETFILES} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} $* -q ${FC} -r "${TMP_MOUNT}" "${TMP_MOUNT}${m}"
+	            ${SETFILES} ${VERBOSE} ${EXCLUDEDIRS} ${FORCEFLAG} ${THREADS} $* -q ${FC} -r "${TMP_MOUNT}" "${TMP_MOUNT}${m}"
 	            umount "${TMP_MOUNT}${m}" || exit 1
 	            rm -rf "${TMP_MOUNT}" || echo "Error cleaning up."
 	        done;
@@ -329,8 +330,9 @@ case "$1" in
 	fi
 	> /.autorelabel || exit $?
 	[ -z "$FORCEFLAG" ] || echo -n "$FORCEFLAG " >> /.autorelabel
-	[ -z "$BOOTTIME" ] || echo -N $BOOTTIME >> /.autorelabel
-	[ -z "$BIND_MOUNT_FILESYSTEMS" ] || echo "-M" >> /.autorelabel
+	[ -z "$BOOTTIME" ] || echo -n "-N $BOOTTIME " >> /.autorelabel
+	[ -z "$BIND_MOUNT_FILESYSTEMS" ] || echo -n "-M " >> /.autorelabel
+	[ -z "$THREADS" ] || echo -n "$THREADS " >> /.autorelabel
 	# Force full relabel if SELinux is not enabled
 	selinuxenabled || echo -F > /.autorelabel
 	echo "System will relabel on next boot"
@@ -342,17 +344,17 @@ esac
 }
 usage() {
 	echo $"""
-Usage: $0 [-v] [-F] [-M] [-f] relabel
+Usage: $0 [-v] [-F] [-M] [-f] [-T nthreads] relabel
 or
-Usage: $0 [-v] [-F] [-B | -N time ] { check | restore | verify }
+Usage: $0 [-v] [-F] [-B | -N time ]  [-T nthreads] { check | restore | verify }
 or
-Usage: $0 [-v] [-F] { check | restore | verify } dir/file ...
+Usage: $0 [-v] [-F] [-T nthreads] { check | restore | verify } dir/file ...
 or
-Usage: $0 [-v] [-F] -R rpmpackage[,rpmpackage...] { check | restore | verify }
+Usage: $0 [-v] [-F] [-T nthreads] -R rpmpackage[,rpmpackage...] { check | restore | verify }
 or
-Usage: $0 [-v] [-F] -C PREVIOUS_FILECONTEXT { check | restore | verify }
+Usage: $0 [-v] [-F] [-T nthreads] -C PREVIOUS_FILECONTEXT { check | restore | verify }
 or
-Usage: $0 [-F] [-M] [-B] onboot
+Usage: $0 [-F] [-M] [-B] [-T nthreads] onboot
 """
 }
 
@@ -371,7 +373,7 @@ set_restore_mode() {
 }
 
 # See how we were called.
-while getopts "N:BC:FfR:l:vM" i; do
+while getopts "N:BC:FfR:l:vMT:" i; do
     case "$i" in
 	B)
 		BOOTTIME=`/bin/who -b | awk '{print $3}'`
@@ -406,6 +408,9 @@ while getopts "N:BC:FfR:l:vM" i; do
 	f)
 		fullFlag=1
 		;;
+	T)
+		THREADS="-T $OPTARG"
+		;;
 	*)
 	    usage
 	    exit 1
diff --git a/policycoreutils/scripts/fixfiles.8 b/policycoreutils/scripts/fixfiles.8
index c4e894e56e8f..9a317d9181e2 100644
--- a/policycoreutils/scripts/fixfiles.8
+++ b/policycoreutils/scripts/fixfiles.8
@@ -6,22 +6,22 @@ fixfiles \- fix file SELinux security contexts.
 .na
 
 .B fixfiles
-.I [\-v] [\-F] [-M] [\-f] relabel
+.I [\-v] [\-F] [-M] [\-f] [\-T nthreads] relabel
 
 .B fixfiles
-.I [\-v] [\-F] { check | restore | verify } dir/file ...
+.I [\-v] [\-F] [\-T nthreads] { check | restore | verify } dir/file ...
 
 .B fixfiles
-.I [\-v] [\-F] [\-B | \-N time ] { check | restore | verify }
+.I [\-v] [\-F] [\-B | \-N time ] [\-T nthreads] { check | restore | verify }
 
 .B fixfiles 
-.I [\-v] [\-F] \-R rpmpackagename[,rpmpackagename...] { check | restore | verify }
+.I [\-v] [\-F] [\-T nthreads] \-R rpmpackagename[,rpmpackagename...] { check | restore | verify }
 
 .B fixfiles
-.I [\-v] [\-F] \-C PREVIOUS_FILECONTEXT  { check | restore | verify }
+.I [\-v] [\-F] [\-T nthreads] \-C PREVIOUS_FILECONTEXT  { check | restore | verify }
 
 .B fixfiles
-.I [-F] [-M] [-B] onboot
+.I [-F] [-M] [-B] [\-T nthreads] onboot
 
 .ad
 
@@ -76,6 +76,11 @@ Bind mount filesystems before relabeling them, this allows fixing the context of
 .B -v
 Modify verbosity from progress to verbose. (Run restorecon with \-v instead of \-p)
 
+.TP
+.B \-T nthreads
+Use parallel relabeling, see
+.B setfiles(8)
+
 .SH "ARGUMENTS"
 One of:
 .TP 
