This paper presents an algorithm for finding approximately optimal policies in very large Markov decision processes by constructing a hierarchical model and then solving it. This strategy sacrifices optimality for the ability to solve larger problems. Our algorithm works efficiently on factored MDPs by constructing a hierarchical structure based on the connectivity properties of the domain and then using that structure to solve for a policy. Within the hierarchical model, we assume upper level transitions are deterministic, although we take non- determinism into account at the bottom level, allowing us to quickly compute a top-down solution. We give a bound on the error incurred by the resulting algorithm and show that it finds good approximate solutions and has total running times (creating + solving the hierarchy) that are significantly less than optimally solving the factored MDP.