We introduce a new algebra associated with a hyperplane arrangement $mathcal{A}$, called the Solomon-Terao algebra $mbox{ST}(mathcal{A},eta)$, where $eta$ is a homogeneous polynomial. It is shown by Solomon and Terao that $mbox{ST}(mathcal{A},eta)$ is Artinian when $eta$ is generic. This algebra can be considered as a generalization of coinvariant algebras in the setting of hyperplane arrangements. The class of Solomon-Terao algebras contains cohomology rings of regular nilpotent Hessenberg varieties. We show that $mbox{ST}(mathcal{A},eta)$ is a complete intersection if and only if $mathcal{A}$ is free. We also give a factorization formula of the Hilbert polynomials when $mathcal{A}$ is free, and pose several related questions, problems and conjectures.