In the 1960's, Dr. John P. Costas, motivated by a SONAR application, began searching for permutation matrices with ideal auto-ambiguity properties. By hand, he found examples of such matrices of size up to N = 12. Unable to find one of size 13, he contacted Professor Solomon Golomb who then provided generation techniques based on the theory of finite fields for creating these matrices, dubbed Costas arrays. The generation methods produce Costas arrays for infinitely many N, but not all N. For example, the techniques can be used to generate arrays for all N <= 31, but no Costas array of size N = 32 or N = 33 has been found. Computer search has previously enumerated all Costas arrays of size N <= 26, and we have just completed the exhaustive (and exhausting!) enumeration of the number of Costas arrays of size 27, a computation which took over 25 years of single CPU time. In addition to this computational result, we have recently made progress on the theory of Costas arrays and have interesting results linking the cross-correlation behavior of the two families of Costas arrays (Welch and Golomb). Families of Costas arrays have nearly optimal cross-correlations when generated over 'safe' primes (primes of the form 2p+1 where p is also prime). The talk will introduce Costas Arrays, discuss the enumeration and cross-correlation results and some open problems.