Background: Across the world, ticks act as vectors of human and animal pathogens. Ticks rely on bacterial endosymbionts, which often share close and complex evolutionary links with tick-borne pathogens. As the prevalence, diversity and virulence potential of tick-borne agents remain poorly understood, there is a pressing need for microbial surveillance of ticks as potential disease vectors. Methodology/Principal Findings: We developed a two-stage protocol that includes 16S-amplicon screening of pooled samples of hard ticks collected from dogs, sheep and camels in Palestine, followed by shotgun metagenomics on individual ticks to detect and characterise tick-borne pathogens and endosymbionts. Two ticks isolated from sheep yielded an abundance of reads from the genus Rickettsia, which were assembled into draft genomes. One of the resulting genomes was highly similar to Rickettsia massiliae strain MTU5. Analysis of signature genes showed that the other represents the first genome sequence of the potential pathogen Candidatus Rickettsia barbariae. Ticks from a dog and a sheep yielded draft genome sequences of Coxiella strains. A sheep tick yielded sequences from the sheep pathogen Anaplasma ovis, while Hyalomma ticks from camels yielded sequences belonging to Francisella-like endosymbionts. From the metagenome of a dog tick from Jericho, we generated a genome sequence of a canine parvovirus. Significance: Here, we have shown how a cost-effective two-stage protocol can be used to detect and characterise tick-borne pathogens and endosymbionts. In recovering genome sequences from an unexpected pathogen (canine parvovirus) and a previously unsequenced pathogen (Candidatus Rickettsia barbariae), we demonstrate the open-ended nature of metagenomics. We also provide evidence that ticks can carry canine parvovirus, raising the possibility that ticks might contribute to the spread of this troublesome virus.