Clinical sleep evaluations currently require multimodal data collection and manual review by human experts, making them expensive and unsuitable for longer term studies. Sleep staging using cardiac rhythm is an active area of research because it can be measured much more easily using a wide variety of both medical and consumer-grade devices. In this study, we applied deep learning methods to create an algorithm for automated sleep stage scoring using the instantaneous heart rate (IHR) time series extracted from the electrocardiogram (ECG). We trained and validated an algorithm on over 10,000 nights of data from the Sleep Heart Health Study (SHHS) and Multi-Ethnic Study of Atherosclerosis (MESA). The algorithm has an overall performance of 0.77 accuracy and 0.66 kappa against the reference stages on a held-out portion of the SHHS dataset for classifying every 30 s of sleep into four classes: wake, light sleep, deep sleep, and rapid eye movement (REM). Moreover, we demonstrate that the algorithm generalizes well to an independent dataset of 993 subjects labeled by American Academy of Sleep Medicine (AASM) licensed clinical staff at Massachusetts General Hospital that was not used for training or validation. Finally, we demonstrate that the stages predicted by our algorithm can reproduce previous clinical studies correlating sleep stages with comorbidities such as sleep apnea and hypertension as well as demographics such as age and gender.