Birds, like mammals, have multiple forms of sleep including rapid eye movement sleep (REM) and slow wave sleep (SWS). It is not known why or how these specialized stages of sleep evolved. For many decades, the overwhelming consensus was that avian sleep was more primitive. This led to the conclusion that complex sleep evolved independently in mammals and birds. Recently, songbirds were found to have surprisingly mammalian-like sleep architecture as well as sleep replay of song, a learned motor skill. In mammals, sleep replay in hippocampal place cells is thought to be a central mechanism for the function of sleep in learning and memory. The well-established co-occurrence of hippocampal replay with slow waves demonstrates the link between global sleep architecture and circuit-level mediators of sleep function. However, sleep has profound effects not only on hippocampal-dependent declarative memory, but also on procedural memory. Song replay, as the only other confirmed exemplar of sleep replay, thus offers a chance to study a similar mechanism within a procedural memory system. I sought to better understand how sleep architecture is expressed across multiple bird species, and how song replay is related to sleep structure. I characterized sleep architecture in budgerigars (Melopsittacus undulatus), finding multiple signs of complex, highly structured, and mammalian-like sleep. These traits included patterns of REM increase and SWS decrease, a stage of intermediate sleep that remained consistent over the night, a 34-minute sleep cycle, and the largest amount of REM found in adults of any bird species to date (26.5%). Furthermore, I demonstrated that a major source of error in earlier studies was the use of constant light, which I found to abolish the circadian rhythm, decrease total sleep, and fragment sleep episodes. Using automated techniques, I went on to confirm recent results on sleep architecture in zebra finches (Taeniopygia guttata) and characterized the sleep/wake cycle over 24 hours. The findings are consistent with mammalian-like patterns of REM increase and SWS decrease, contradicting older reports of songbird sleep. I also observed a 38-minute sleep cycle in zebra finches. These results indicate that complex sleep structure is most likely to includes the majority of extant species of birds (songbirds and parrots), and promotes re-evaluation of the evolutionary history of complex sleep in birds and in mammals. As part of the work on sleep replay, I was involved in an effort to develop techniques for chronic multielectrode array recordings in zebra finches. These methods are described here in detail to facilitate replication of this technique, including implant construction, surgery, recording, and spikesorting. I used this technique to record from the nucleus robustus of the arcopallium (RA), the motor cortex analogue of the song system. By combining chronic recordings of RA activity with polysomnography over multiple sleep/wake cycles, I was able to examine the relationship between song replay and sleep structure. Song replay was most strongly linked to non-REM, occurred during periods of higher slow wave activity, and often co-occurred with local slow waves. Replay events most often occurred at or near real-time, in contrast with the highly compressed replay of the hippocampus. These results establish for the first time similarities and differences in sleep replay comparing declarative and procedural memories. In sum these results show that highly complex sleep traits manifest across songbirds and parrots, and that complex sleep architecture is linked to song replay. This supports the hypothesis that shared attributes of avian and mammalian sleep are derived from a common precursor, and helps to illuminate underlying mechanisms by which complex sleep can affect procedural memory.