We give a general method for constructing explicit and natural operations on the Hochschild complex of algebras over any prop with A∞-multiplication—we think of such algebras as A∞-algebras “with extra structure”. As applications, we obtain an integral version of the Costello–Kontsevich–Soibelman moduli space action on the Hochschild complex of open TCFTs, the Tradler–Zeinalian and Kaufmann actions of Sullivan diagrams on the Hochschild complex of strict Frobenius algebras, and give applications to string topology in characteristic zero. Our main tool is a generalization of the Hochschild complex.