diff --git a/share/man/man4/pf.4 b/share/man/man4/pf.4
--- a/share/man/man4/pf.4
+++ b/share/man/man4/pf.4
@@ -102,8 +102,13 @@
 .Nm
 to also filter on the loopback output hook.
 This is typically used to allow redirect rules to adjust the source address.
-.It net.pf.request_maxcount
+.It Va net.pf.request_maxcount
 The maximum number of items in a single ioctl call.
+.It Va net.pf.rdr_srcport_rewrite_tries
+The maximum number of times to try and find a free source port when handling
+redirects.
+Such rules are typically applied to external traffic, so an exhaustive search
+may be too expensive.
 .El
 .Pp
 Read only
diff --git a/share/man/man5/pf.conf.5 b/share/man/man5/pf.conf.5
--- a/share/man/man5/pf.conf.5
+++ b/share/man/man5/pf.conf.5
@@ -1407,7 +1407,11 @@
 .Ar rdr
 rule may cause the source port to be modified if doing so avoids a conflict
 with an existing connection.
-A random source port in the range 50001-65535 is chosen in this case.
+A random source port in the range 50001-65535 is chosen in this case; to
+avoid excessive CPU consumption, the number of searches for a free port is
+limited by the
+.Va net.pf.rdr_srcport_rewrite_tries
+sysctl.
 Port numbers are never translated with a
 .Ar binat
 rule.
diff --git a/sys/netpfil/pf/pf_lb.c b/sys/netpfil/pf/pf_lb.c
--- a/sys/netpfil/pf/pf_lb.c
+++ b/sys/netpfil/pf/pf_lb.c
@@ -52,6 +52,13 @@
 #include <net/pfvar.h>
 #include <net/if_pflog.h>
 
+/*
+ * Limit the amount of work we do to find a free source port for redirects that
+ * introduce a state conflict.
+ */
+#define	V_pf_rdr_srcport_rewrite_tries	VNET(pf_rdr_srcport_rewrite_tries)
+VNET_DEFINE_STATIC(int, pf_rdr_srcport_rewrite_tries) = 16;
+
 #define DPFPRINTF(n, x)	if (V_pf_status.debug >= (n)) printf x
 
 static void		 pf_hash(struct pf_addr *, struct pf_addr *,
@@ -822,6 +829,7 @@
 		break;
 	case PF_RDR: {
 		struct pf_state_key_cmp key;
+		int tries;
 		uint16_t cut, low, high, nport;
 
 		reason = pf_map_addr(pd->af, r, saddr, naddr, NULL, NULL, sn);
@@ -873,11 +881,15 @@
 		if (!pf_find_state_all_exists(&key, PF_OUT))
 			break;
 
+		tries = 0;
+
 		low = 50001;	/* XXX-MJ PF_NAT_PROXY_PORT_LOW/HIGH */
 		high = 65535;
 		cut = arc4random() % (1 + high - low) + low;
 		for (uint32_t tmp = cut;
-		    tmp <= high && tmp <= UINT16_MAX; tmp++) {
+		    tmp <= high && tmp <= UINT16_MAX &&
+		    tries < V_pf_rdr_srcport_rewrite_tries;
+		    tmp++, tries++) {
 			key.port[0] = htons(tmp);
 			if (!pf_find_state_all_exists(&key, PF_OUT)) {
 				/* Update the source port. */
@@ -885,7 +897,9 @@
 				goto out;
 			}
 		}
-		for (uint32_t tmp = cut - 1; tmp >= low; tmp--) {
+		for (uint32_t tmp = cut - 1;
+		    tmp >= low && tries < V_pf_rdr_srcport_rewrite_tries;
+		    tmp--, tries++) {
 			key.port[0] = htons(tmp);
 			if (!pf_find_state_all_exists(&key, PF_OUT)) {
 				/* Update the source port. */