We study Haar unitary random matrices with permuted entries. For a sequence of permutations $\left(σ_N\right)_N$, where $σ_N$ acts on $N\times N$ matrices we identify conditions under which the $\ast$--distribution of permuted Haar unitary matrices $U_N^{σ_N}$ is asymptotically circular and free from the unpermuted sequence $U_N$. We show that this convergence takes place in the almost sure sense. Moreover we show that our conditions on the sequence of permutations are generic in the sense that are almost surely satisfied by a sequence of random permutations.