We explore the construction and stability of asymptotically anti-de Sitter Euclidean wormholes in a variety of models. In simple ad hoc low-energy models, it is not hard to construct two-boundary Euclidean wormholes that dominate over disconnected solutions and which are stable (lacking negative modes) in the usual sense of Euclidean quantum gravity. Indeed, the structure of such solutions turns out to strongly resemble that of the Hawking-Page phase transition for AdS-Schwarzschild black holes, in that for boundary sources above some threshold we find both a large' and a small' branch of wormhole solutions with the latter being stable and dominating over the disconnected solution for large enough sources. We are also able to construct two-boundary Euclidean wormholes in a variety of string compactifications that dominate over the disconnected solutions we find and that are stable with respect to field-theoretic perturbations. However, as in classic examples investigated by Maldacena and Maoz, the wormholes in these UV-complete settings always suffer from brane-nucleation instabilities (even when sources that one might hope would stabilize such instabilities are tuned to large values). This indicates the existence of additional disconnected solutions with lower action. We discuss the significance of such results for the factorization problem of AdS/CFT.