Massive increases in production and consumption of digital media are motivating cloud 'video encoding as a service.' In this paper, we explore efficient platforms for supporting such services. Specifically, we explore transcoding performance on a software encoder and two hardware-accelerated encoders representing widely different points in the hardware acceleration design space, as well as interference effects when heterogenous encoders are run concurrently. Using results from our exploratory study, we next propose a framework for providing video encoding as a service on a single server, and implement a prototype of the framework in a system called Catalyst. Catalyst accepts transcoding tasks and intelligently uses all available resources, including software and hardware-accelerated encoders, to maximize throughput while respecting task deadlines, and provides a foundational building block for a cluster-based cloud video encoding service. We evaluate Catalyst using a synthetic transcoding workload designed to emulate an IP-TV/Cloud-DVR workload. Evaluation results show that Catalyst can significantly increase throughput while meeting task deadlines compared to naive use of hardware-accelerated encoding.