Technical Abstract: Honey bees (Apis mellifera) are an important agricultural commodity providing honey, other bee products, and pollination services. Domesticated honey bees in the United States and elsewhere have been in decline in recent years, despite an increasing need for honey bee pollination services. This fact is often blamed on increasing challenges from pests and pathogens, as well as episodes of severe decline such as the enigmatic 'colony collapse disorder'. The ectoparasitic mite Varroa destructor has emerged as the primary pest of domestic honey bees (Apis mellifera). Here we present an initial survey of the V. destructor genome carried out to advance our understanding of Varroa biology and to identify new avenues for mite control. This sequence survey provides immediate resources for molecular and population-genetic analyses of Varroa-Apis interactions and defines the challenges ahead for a comprehensive Varroa genome project. The genome size was estimated by flow cytometry to be 565 Mbp, larger than most sequenced insects but modest relative to some other Acari. Genomic DNA pooled from ~1,000 mites was sequenced to 4.3X coverage with 454 pyrosequencing. The 2.4 Gbp of sequencing reads were assembled into 184,094 contigs, totaling 294 Mbp of sequence after filtering. Genic sequences with homology to other eukaryotic genomes were identified on 13,031 contigs. Alignment of protein sequence blocks conserved among V. destructor and four other arthropod genomes indicated a higher rate of sequence divergence within this mite lineage relative to the tick Ixodes scapularis. A number of microbes potentially associated with V. destructor were identified in the sequence survey, including numerous contigs (totaling ~300 Kbp) deriving from one or more bacterial species of the Actinomycetales. The presence of this bacterium was confirmed in individual mites by PCR assay, and its presence was found to vary significantly by age and sex. Fragments of a novel virus related to the Baculoviridae were also identified in the survey, providing insights into the metagenomic environment within Varroa. Within the nuclear Varroa sequences, the rate of single nucleotide polymorphisms (SNPs) in the pooled sample was estimated to be low, 6.2 x 10-5, consistent with what is known about the historical demography and life history of the species. This survey has provided general tools for the research community and novel directions for investigating the biology and control of Varroa mites. Ongoing development of Varroa genomic resources will be a boon for comparative genomics of under-represented arthropods, and will further enhance the honey bee and its associated pathogens as a model system for studying host-pathogen interactions.