To identify the processes shaping vertebrate sex chromosomes during the early stages of their evolution, it is necessary to study systems in which genetic sex determination was recently acquired. Previous cytogenetic studies suggested that threespine stickleback fish (Gasterosteus aculeatus) do not have a heteromorphic sex chromosome pair, although recent genetic studies found evidence of an XY genetic sex-determination system. Using fluorescence in situ hybridization (FISH), we report that the threespine stickleback Y chromosome is heteromorphic and has suffered both inversions and deletion. Using the FISH data, we reconstruct the rearrangements that have led to the current physical state of the threespine stickleback Y chromosome. These data demonstrate that the threespine Y is more degenerate than previously thought, suggesting that the process of sex chromosome evolution can occur rapidly following acquisition of a sex-determining region.