We consider the optimal stopping problem of a Markov process {x(t) : t >= 0} when the controller is allowed to stop only at the arrival times of a signal, that is, at a sequence of instants {tau(n) : n >= 1} independent of {x(t) : t >= 0}. We solve in detail this problem for general Markov-Feller processes with compact state space when the interarrival times of the signal are independent identically distributed random variables. In addition, we discuss several extensions to other signals and to other cases of state spaces. These results generalize the works of several authors where {x(t) : t >= 0} was a diffusion process and where the signal arrives at the jump times of a Poisson process.