In this dissertation we consider certain closed subvarieties of the flag variety, known as Hessenberg varieties. We prove that Hessenberg varieties corresponding to nilpotent elements which are regular in a Levi factor are paved by affines. We provide a partial reduction from paving Hessenberg varieties for arbitrary elements to paving those corresponding to nilpotent elements. As a consequence, we generalize results of Tymoczko asserting that Hessenberg varieties for regular nilpotent elements in the classical cases and arbitrary elements of gl_n(C) are paved by affines. For example, our results prove that any Hessenberg variety corresponding to a regular element is paved by affines. As a corollary, in all these cases the Hessenberg variety has no odd dimensional cohomology.