A polymerase chain reaction (PCR) primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the problem of designing a pair of primers with prescribed degeneracy that match a maximum number of given input sequences. Such problems occur, for example, when studying a family of genes that is known only in part or is known in a related species. We discuss the complexity of several versions of the problem and give approximation algorithms for one simplified variant. On the basis of these algorithms, we developed a program called HYDEN for designing highly degenerate primers for a set of genomic sequences. We describe HYDEN, and report on its success in several applications for identifying olfactory receptor genes in mammals.