We solve the martingale optimal transport problem for cost functionals represented by optimal stopping problems. The measure-valued martingale approach developed in [A. M. G. Cox and S. Kallblad, SIAM T. Control Opton., 55 (2017), pp. 3409-3436] allows us to obtain an equivalent infinite dimensional controller-stopper problem. We use the stochastic Perron's method and characterize the finite dimensional approximation as a viscosity solution to the corresponding HJB equation. It turns out that this solution is the concave envelope of the cost function with respect to the atoms of the terminal law. We demonstrate the results by finding explicit solutions for a class of cost functions.