Regular semisimple Hessenberg varieties are subvarieties of the flag variety Flag(ℂn) arising naturally at the intersection of geometry, representation theory, and combinatorics. Recent results of Abe, Horiguchi, Masuda, Murai, and Sato as well as of Abe, DeDieu, Galetto, and Harada relate the volume polynomials of regular semisimple Hessenberg varieties to the volume polynomial of the Gelfand–Zetlin polytope GZ(λ) for λ = (λ1, λ2, …, λn). In the main results of this paper we use and generalize tools developed by Anderson and Tymoczko, by Kiritchenko, Smirnov, and Timorin, and by Postnikov in order to derive an explicit formula for the volume polynomials of regular semisimple Hessenberg varieties in terms of the volumes of certain faces of the Gelfand–Zetlin polytope, and also exhibit a manifestly positive, combinatorial formula for their coefficients with respect to the basis of monomials in the αi:= λi − λi+1. In addition, motivated by these considerations, we carefully analyze the special case of the permutohedral variety, which is also known as the toric variety associated to Weyl chambers. In this case, we obtain an explicit decomposition of the permutohedron (the moment map image of the permutohedral variety) into combinatorial (n − 1)-cubes, and also give a geometric interpretation of this decomposition by expressing the cohomology class of the permutohedral variety in Flag(ℂn) as a sum of the cohomology classes of a certain set of Richardson varieties.