Recent studies of humans, dogs and rodents have started to discover the genetic underpinnings of high altitude adaptations, yet amphibians have received little attention in this respect. To identify possible signatures of adaptation to altitude, we performed a genome scan of 15 557 single nucleotide polymorphisms (SNPs) obtained with restriction site-associated DNA sequencing of pooled samples from 11 populations of Andrew's toad (Bufo andrewsi) from the edge of the Tibetan Plateau, spanning an altitudinal gradient from 1690 to 2768 m.a.s.l. We discovered significant geographic differentiation among all sites, with an average FST = 0.023 across all SNPs. Apart from clear patterns of isolation by distance, we discovered numerous outlier SNPs showing strong associations with variation in altitude (1394 SNPs), average annual temperature (1859 SNPs) or both (1051 SNPs). Levels and patterns of genetic differentiation in these SNPs were consistent with the hypothesis that they have been subject to directional selection and reflect adaptation to altitudinal variation among the study sites. Genes with footprints of selection were significantly enriched in binding and metabolic processes. Several genes potentially related to high altitude adaptation were identified, although the identity and functional significance of most genomic targets of selection remain unknown. In general, the results provide genomic support for results of earlier common garden and low coverage genetic studies that have uncovered substantial adaptive differentiation along altitudinal and latitudinal gradients in amphibians.