© 2018 American Physical Society. We introduce several classes of quantum combinatorial designs, namely quantum Latin squares, cubes, hypercubes, and a notion of orthogonality between them. A further introduced notion, quantum orthogonal arrays, generalizes all previous classes of designs. We show that mutually orthogonal quantum Latin arrangements can be entangled in the same way in which quantum states are entangled. Furthermore, we show that such designs naturally define a remarkable class of genuinely multipartite highly entangled states called k-uniform, i.e., multipartite pure states such that every reduction to k parties is maximally mixed. We derive infinitely many classes of mutually orthogonal quantum Latin arrangements and quantum orthogonal arrays having an arbitrary large number of columns. The corresponding multipartite k-uniform states exhibit a high persistency of entanglement, which makes them ideal candidates to develop multipartite quantum information protocols.