  The $d$-Simultaneous Conjugacy problem in the symmetric group $S_n$ asks
whether there exists a permutation $\tau \in S_n$ such that $b_j = \tau^{-1}a_j
\tau$ holds for all $j = 1,2,\ldots, d$, where $a_1, a_2,\ldots , a_d$ and
$b_1, b_2,\ldots , b_d$ are given sequences of permutations in $S_n$. The time
complexity of existing algorithms for solving the problem is $O(dn^2)$. We show
that for a given positive integer $d$ the $d$-Simultaneous Conjugacy problem in
$S_n$ can be solved in $o(n^2)$ time.
