American Foulbrood (AFB) of honey bees caused by the spore-forming bacterium Paenibacillus larvae is a notifiable epizootic in most countries. Authorities often consider a rigorous eradication policy the only sustainable control measure. However, early diagnosis of infected but not yet diseased colonies opens up the possibility of ridding these colonies of P. larvae spores by the shook swarm method, thus preventing colony destruction by AFB or official control orders. Therefore, surveillance of bee colonies for P. larvae infection followed by appropriate sanitary measures is a very important intervention to control AFB. For the detection of P. larvae spores in infected colonies, samples of brood comb honey, adult bees, or hive debris are commonly used. We here present our results from a comparative study on the suitability of these matrices in reliably and correctly detecting P. larvae spores contained in these matrices. Based on the sensitivity and limit of detection of P. larvae spores in samples from hive debris, adult bees, and brood comb honey, we conclude that the latter two are equally well-suited for AFB surveillance programs. Hive debris samples should only be used when it is not possible to collect honey or adult bee samples from brood combs.