This letter deals with the time evolution of a qubit weakly coupled to a reservoir which has a symmetry-broken state with long-range order at finite temperatures. In particular, we model the ordered reservoir by a standard BCS superconductor with s-wave pairing. We study the reduced density matrix of a qubit using both the time-convolutionless and Nakajima-Zwanzig approximations. We study different kinds of couplings between the qubit and the superconducting bath. We find that ordering in the superconducting bath generically leads to an unfavorable non-Markovian faster-than-exponential decay of the qubit coherence. On the other hand, a coupling of the qubit to the non-ordered sector of the bath can result in a Markovian decoherence of the qubit with a drastic reduction of the decoherence rate. Since these behaviors are endemic to the ordered phase, qubits can serve as useful probes of continuous phase transitions in their environment. We also briefly discuss the validity of our main result, faster-than-exponential decay of the qubit coherences, for a qubit coupled to a generic ordered bath with a spontaneously broken continuous symmetry at finite temperatures.