Quantum sensors and qubits are usually two-level systems (TLS), the quantum analogues of classical bits assuming binary values 0 or 1. They are useful to the extent to which superpositions of 0 and 1 persist despite a noisy environment. The standard prescription to avoid decoherence of solid-state qubits is their isolation by means of extreme dilution in ultrapure materials. We demonstrate a different strategy using the rare-earth insulator LiY1-xTbxF4 (x = 0.001) which realizes a dense random network of TLS. Some TLS belong to strongly interacting Tb3+ pairs whose quantum states, thanks to localization effects, form highly coherent qubits with 100-fold longer coherence times than single ions. Our understanding of the underlying decoherence mechanisms-and of their suppression-suggests that coherence in networks of dipolar coupled TLS can be enhanced rather than reduced by the interactions.|Quantum coherence is hard to maintain in solid-state systems, as interactions usually lead to fast dephasing. Exploiting disorder effects and interactions, highly coherent two-level systems have now been realized in a rare-earth insulator compound.