An appliance migration mechanism (AMM) optimizes migration of a live virtual appliance with virtual objects between cloud environments to minimize temporary connections that use significant cloud resources during the migration. The AMM determines a cost of connections of each virtual object in the virtual appliance and produces an order of migration for the virtual objects. The cost of connections of the virtual objects may be determined by the total number of connections and the maximum number of connections. Alternatively the cost of the connections of the virtual objects for migration could be determined by a weighting the costs of the connections where the weighting may consider loading or other factors on the connection.