Specific wiring of gene-regulatory networks is likely to underlie much of the phenotypic difference between species, but the extent of lineage-specific regulatory architecture remains poorly understood. The essential vertebrate transcriptional repressor REST (RE1-Silencing Transcription Factor) targets many neural genes during development of the preimplantation embryo and the central nervous system, through its cognate DNA motif, the RE1 (Repressor Element 1). Here we present a comparative genomic analysis of REST recruitment in multiple species by integrating both sequence and experimental data. We use an accurate, experimentally validated Position-Specific Scoring Matrix method to identify REST binding sites in multiply aligned vertebrate genomes, allowing us to infer the evolutionary origin of each of 1,298 human RE1 elements. We validate these findings using experimental data of REST binding across the whole genomes of human and mouse. We show that one-third of human RE1s are unique to primates: These sites recruit REST in vivo, target neural genes, and are under purifying evolutionary selection. We observe a consistent and significant trend for more ancient RE1s to have higher affinity for REST than lineage-specific sites and to be more proximal to target genes. Our results lead us to propose a model where new transcription factor binding sites are constantly generated throughout the genome; thereafter, refinement of their sequence and location consolidates this remodeling of networks governing neural gene regulation.