We investigate instantons on manifolds with Killing spinors and their cones. Examples of manifolds with Killing spinors include nearly Kaehler 6-manifolds, nearly parallel G_2-manifolds in dimension 7, Sasaki-Einstein manifolds, and 3-Sasakian manifolds. We construct a connection on the tangent bundle over these manifolds which solves the instanton equation, and also show that the instanton equation implies the Yang-Mills equation, despite the presence of torsion. We then construct instantons on the cones over these manifolds, and lift them to solutions of heterotic supergravity. Amongst our solutions are new instantons on even-dimensional Euclidean spaces, as well as the well-known BPST, quaternionic and octonionic instantons.