Recent methods for localization of microphones in a microphone array exploit sound sources at a priori unknown locations. This is convenient for ad-hoc arrays, as it requires little additional infrastructure. We propose a flexible localization algorithm by first recognizing the problem as an instance of multidimensional unfolding (MDU)—a classical problem in Euclidean geometry and psychometrics—and then solving the MDU as a special case of Euclidean distance matrix (EDM) completion. We solve the EDM completion using a semidefinite relaxation. In contrast to existing methods, the semidefinite formulation allows us to elegantly handle missing pairwise distance information, but also to incorporate various prior information about the distances between the pairs of microphones or sources, bounds on these distances, or ordinal information such as “microphones 1 and 2 are more apart than microphones 1 and 15”. The intuition that this should improve the localization performance is confirmed by numerical experiments.