Culturable psychrotolerant bacteria were isolated from the top snow on the high Antarctic Plateau surrounding the research station Concordia. A total of 80 isolates were recovered from two different isolation sites (a distant pristine site and a site near the secondary runway). All isolates were classified to the genus Paenibacillus by 16S rRNA gene phylogenetic analysis. ERIC-PCR fingerprinting indicated that the isolates were not all clonal. All isolates grew well from 4 to 37 °C and were resistant to ampicillin and streptomycin. The isolates were compared to 29 Paenibacillus isolates, which were previously recovered from inside the Concordia research station. One of these inside isolates showed ERIC- and REP-PCR fingerprinting profiles identical to those of the runway isolates. The latter suggested that dissemination of culturable Paenibacillus strains between the harsh Antarctic environment and the inside of the Concordia research station occurred. In addition, inducible prophages, which are potentially involved in horizontal dissemination of genes, were detected in Paenibacillus isolates recovered from outside and inside the station. The highest lysogeny was observed in strains harvested from the hostile environment outside the station.