Given any twisting cochain t:C→A , where C is a connected, coaugmented chain coalgebra and A is an augmented chain algebra over an arbitrary commutative ring R, we construct a twisted extension of chain complexes Full-size image (1 K) of which both the well-known Hochschild complex of an augmented, associative algebra and the coHochschild complex of a coaugmented, coassociative coalgebra [13] are special cases. We therefore call H(t) the Hochschild complex of the twisting cochain t. We explore the extent of the naturality of the Hochschild complex construction and apply the results of this exploration to determining conditions under which H(t) admits multiplicative or comultiplicative structure. In particular, we show that the Hochschild complex on a chain Hopf algebra always admits a natural comultiplication. Furthermore, when A is a chain Hopf algebra, we determine conditions under which H(t) admits an rth-power map extending the usual rth-power map on A and lifting the identity on C. As special cases, we obtain that both the Hochschild complex of any cocommutative Hopf algebra and the coHochschild complex of the normalized chain complex of a simplicial double suspension admit power maps.