Potato cyst nematodes (PCN) are economically important pests with a worldwide distribution in all temperate regions where potatoes are grown. Because above ground symptoms are non-specific, and detection of cysts in the soil is determined by the intensity of sampling, infestations are frequently spread before they are recognised. PCN cysts are resilient and persistent; their cargo of eggs can remain viable for over two decades, and thus once introduced PCN are very difficult to eradicate. Various control methods have been proposed, with resistant varieties being a key environmentally friendly and effective component of an integrated management programme. Wild and landrace relatives of cultivated potato have provided a source of PCN resistance genes that have been used in breeding programmes with varying levels of success. Producing a PCN resistant variety requires concerted effort over many years before it reaches what can be the biggest hurdle—commercial acceptance. Recent advances in potato genomics have provided tools to rapidly map resistance genes and to develop molecular markers to aid selection during breeding. This review will focus on the translation of these opportunities into durably PCN resistant varieties.