With the rapid extension of clinical data and knowledge, decision making becomes a complex task for manual sleep staging. In this process, there is a need for integrating and analyzing information from heterogeneous data sources with high accuracy. This paper proposes a novel decision support algorithm—Symbolic Fusion for sleep staging application. The proposed algorithm provides high accuracy by combining data from heterogeneous sources, like EEG, EOG and EMG. This algorithm is developed for implementation in portable embedded systems for automatic sleep staging at low complexity and cost. The proposed algorithm proved to be an efficient design support method and achieved up to 76% overall agreement rate on our database of 12 patients.