Costas arrays are useful in radar and sonar engineering, and many other settings in which optimal 2-D autocorrelation is needed: they are permutation matrices in which the vectors joining different pairs of ones are all distinct. We prove that the density of Costas arrays among permutation matrices decays exponentially, solving a core problem in the theory of Costas arrays. The proof combines ideas from random graph theory with tools from probabilistic combinatorics.