Sleep staging is a vital process conducted in order to analyze polysomnographic data. To facilitate prompt interpretation of these recordings, many automatic sleep staging methods have been proposed. These methods rely on bio-signal recordings, which include electroencephalography, electrocardiography, electromyography, electrooculography, respiratory, pulse oximetry and others. However, advanced, uncomplicated and swift sleep-staging-evaluation is still needed in order to improve the existing polysomnographic data interpretation. The present review focuses on automatic sleep staging methods through bio-signal recording including current and future challenges.