I will discuss how polynomials with a non-hermitian orthogonality on a contour in the complex plane arise in certain random tiling problems. In the case of periodic weightings the orthogonality is matrixvalued. In work with Maurice Duits (KTH Stockholm) the Riemann-Hilbert problem for matrix valued orthogonal polynomials was used to obtain asymptotics for domino tilings of the two-periodic Aztec diamond. This model is remarkable since it gives rise to a gaseous phase, in addition to the more common solid and liquid phases.