An interesting "accidental cancellation" in the Standard Model between the leading production diagrams makes the search for a Higgs boson in association with a single top quark (tHq) a powerful probe for new physics. I will motivate a "strawman scenario" for the interpretation of the results, and present the first search for the production of tHq, using data samples collected by the CMS detector in pp collisions at center-of-mass energy of 8 TeV corresponding to an integrated luminosity of 19.7 fb^-1. The search exploits a variety of top quark and Higgs boson decay modes resulting in final states with photons, bottom quarks, or multileptons, and employs a variety of machine learning techniques to maximize the sensitivity to the signal. The present analysis is optimized for a scenario where the Yukawa coupling has sign opposite to the standard model prediction, that would result in a large enhancement of the signal cross section. In absence of a visible excess of candidate signal events over the background predictions, this analysis sets an upper limit on anomalous tHq production. I will conclude the seminar by extrapolating the current sensitivity to Run II conditions and beyond, and discussing the lessons we learned during the development of the Run I analysis.