A minimal surface in a random environment (MSRE) is a surface which minimizes the sum of its elastic energy and its environment potential energy, subject to prescribed boundary conditions. Apart from their intrinsic interest, such surfaces are further motivated by connections with disordered spin systems and first-passage percolation models. We wish to study the geometry of $d$-dimensional minimal surfaces in a $(d+n)$-dimensional random environment. Specializing to a model that we term harmonic MSRE, in an ``independent'' random environment, we rigorously establish bounds on the geometric and energetic fluctuations of the minimal surface, as well as versions of the scaling relation $χ=2ξ+d-2$ that ties together these two types of fluctuations. In particular, we prove, for all values of $n$, that the surfaces are delocalized in dimensions $d\le 4$ and localized in dimensions $d\ge 5$. Moreover, the surface delocalizes with power-law fluctuations when $d\le 3$ and sub-power-law fluctuations when $d=4$. Our localization results apply also to harmonic minimal surfaces in a periodic random environment.