Let L/K be an S_n-extension of number fields. We consider the problem of finding the least prime of K whose Frobenius in Gal(L/K) is an n-cycle under the assumption of Artin's holomorphy conjecture for Artin L-functions. As a special case we will discuss S_n-extensions of the rational numbers which are unramified over a quadratic extension where we obtain an improvement over previously known bounds. We will also discuss other choices of Galois groups and conjugacy classes where an unconditional improvement over previously known upper bounds is possible.