We introduce the term protonormal to refer to a subgroup H of a group G such that for every x in G the subgroups x(-1) Hx and H commute as sets. If moreover (G, H) is a Hecke pair we show that the Hecke algebra H(G, H) is generated by the range of a canonical partial representation of G vanishing on H. As a consequence we show that there exists a maximum C*-norm on R(G, H), generalizing previous results by Brenken, Hall, Laca, Larsen, Kaliszewski, Landstad and Quigg. When there exists a normal subgroup N of G, containing H as a normal subgroup, we prove a new formula for the product of the generators and give a very clean description of R(G, H) in terms of generators and relations. We also give a description of R(G, H) as a crossed product relative to a twisted partial action of the group GIN on the group algebra of N/H. Based on our presentation of H(G, H) in terms of generators and relations we propose a generalized construction for Hecke algebras in case (G, H) does not satisfy the Hecke condition. (C) 2008 Elsevier Inc. All rights reserved.