It is well-known that severe pain and powerful pain medications cause short- and long-term damage to the developing nervous system of newborns. Caregivers routinely use physiological vital signs [Heart Rate (HR), Respiration Rate (RR), Oxygen Saturation (SR)] to monitor post-surgical pain in the Neonatal Intensive Care Unit (NICU). Here we present a novel approach that combines continuous, non-invasive monitoring of these vital signs and Computer Vision/Deep Learning to make automatic neonate pain detection with an accuracy of 74% AUC, 67.59% mAP. Further, we report for the first time our Early Pain Detection (EPD) approach that explores prediction of the time to onset of post-surgical pain in neonates. Our EPD can alert NICU workers to postoperative neonatal pain about 5 to 10 minutes prior to pain onset. In addition to alleviating the need for intermittent pain assessments by busy NICU nurses via long-term observation, our EPD approach creates a time window prior to pain onset for the use of less harmful pain mitigation strategies. Through effective pain mitigation prior to spinal sensitization, EPD could minimize or eliminate severe post-surgical pain and the consequential need for powerful analgesics in post-surgical neonates.