This paper provides a homological algebraic foundation for generalizations of classical Hecke algebras introduced in (1999, A. Sevostyanov, Comm. Math. Phys. 204, 137). These new Hecke algebras are associated to triples of the form (A, A 0 , =), where A is an associative algebra over a field k containing subalgebra A 0 with augmentation =: A 0 Ä k. These algebras are connected with cohomology of associative algebras in the sense that for every left A-module V and right A-module W the Hecke algebra associated to triple (A, A 0 , =) naturally acts in the A 0 -cohomology and A 0 -homology spaces of V and W, respectively. We also introduce the semi-infinite cohomology functor for associative algebras and define modifications of Hecke algebras acting in semi-infinite cohomology spaces. We call these algebras semi-infinite Hecke algebras. As an example we realize the W-algebra W k (g) associated to a complex semisimple Lie algebra g as a semi-infinite Hecke algebra. Using this realization we explicitly calculate the algebra W k (g) avoiding the bosonization technique used in (1992, B.