Deriving a custom architecture for H.264 video compression based motion estimation is a complex hardware design problem. The problem is complicated by the plethora of design options in the H.264 standard. To derive an efficient architecture, the designer must select between suitable algorithms, allocate computational resources to a custom datapath architecture, and schedule operations onto that architecture, while subject to constraints on both area and execution time. Design space exploration (DSE) addresses the design optimization problem by automating or semi-automating trade-off analysis. We use a DSE tool, DesertFD, to derive architectures for the motion estimation modules of a H.264 encoder. DesertFD is a domain-independent DSE tool which facilitates the representation and pruning of a design space using constraint satisfaction. Using post synthesis data for resource components, we use DesertFD to explore possible architectural solutions for H.264 motion estimation, subject to various area and latency constraints. Our results indicate that UMHEX algorithm is selected for tight area constraints while a five-step-search 5SS algorithm is selected otherwise.