  Let $G$ be a finite group, $H \le G$ a subgroup, $R$ a commutative ring, $A$
an $R$-algebra, and $\alpha$ an action of $G$ on $A$ by $R$-algebra
automorphisms. Following Baker, we associate to this data the \emph{skew Hecke
algebra} $\mathcal{H}_{R}(G,H,A,\alpha)$, which is the convolution algebra of
$H$-invariant functions from $G/H$ to $A$.
  In this paper we study the basic structure of these algebras, proving for
skew Hecke algebras a number of common generalisations of results about skew
group algebras and results about Hecke algebras of finite groups. We show that
skew Hecke algebras admit a certain double coset decomposition. We construct an
isomorphism from $\mathcal{H}_{R}(G,H,A,\alpha)$ to the algebra of
$G$-invariants in the tensor product $A \otimes \mathrm{End}_{R} (
\mathrm{Ind}_{H}^{G} R )$. We show that if $|G|$ is a unit in $A$, then
$\mathcal{H}_{R}(G,H,A,\alpha)$ is isomorphic to a corner ring inside the skew
group algebra $A \rtimes G$.
  Alongside our main results, we show that the construction of skew Hecke
algebras is compatible with certain group-theoretic operations, restriction and
extension of scalars, certain cocycle perturbations of the action, gradings and
filtrations, and the formation of opposite algebras. The main results are
illustrated in the case where $G = S_3$, $H = S_2$, and $\alpha$ is the natural
permutation action of $S_3$ on the polynomial algebra $R[x_1,x_2,x_3]$.
