A system and method for building virtual appliances using a repository metadata server and a dependency resolution service is provided. In particular, a hosted web service may provide a collaborative environment for managing origin repositories and software dependencies, whereby remote clients may follow a simple and repeatable process for creating virtual appliances. For example, the repository metadata server may cache and parse metadata associated with an origin repository, download software from the origin repository, and generate resolution data that can be used by the dependency resolution service. The dependency resolution service may then use the resolution data to resolve dependencies for a package selected for an appliance, wherein the dependencies may include packages that are required, recommended, suggested, banned, or otherwise a dependency for the selected package.