A method and system for integrated server-storage deployment planning for virtual appliances is provided. One implementation involves determining a performance cost in deploying the virtual appliance to different pairings of candidate host and storage subsystems. A host and storage subsystem pair is preferentially selected among the candidate pairings, a pairing of a host and storage subsystem with certain performance cost to satisfy performance requirements of the virtual appliance. Deployment planning may further involve deploying a virtual appliance on one or more appropriate spatially proximate hosts and storage subsystems that exhibit certain preferable connectivity and path capacity to satisfy the performance requirements of the virtual appliance.