The Ulam distance of two permutations on [n] is n minus the length of their longest common subsequence. In this paper, we show that for every \varepsilon>0, there exists some \alpha>0, and an infinite set \Gamma \subseteq \mathbb{N}, such that for all n\in\Gamma, there is an explicit set C_n of (n!)^{\alpha} many permutations on [n], such that every pair of permutations in C_n has pairwise Ulam distance at least (1-\varepsilon) n. Moreover, we can compute the i^th permutation in C_n in poly(n) time and can also decode in poly(n) time, a permutation \pi on [n] to its closest permutation \pi^* in C_n, if the Ulam distance of \pi and \pi^* is less than (1-\varepsilon) n/4 . Previously, it was implicitly known by combining works of Goldreich and Wigderson [Israel Journal of Mathematics'23] and Farnoud, Skachek, and Milenkovic [IEEE Transactions on Information Theory'13] in a black-box manner, that it is possible to explicitly construct (n!)^{\Omega(1)} many permutations on [n], such that every pair of them have pairwise Ulam distance at least (1-\varepsilon) n/6, for any \varepsilon>0, and the bound on the distance can be improved to (1-\varepsilon) n/4 if the construction of Goldreich and Wigderson is directly analyzed in the Ulam metric.