Salutogenic orientation is a health promotion paradigm focusing on the resources of the individual. This study analyzed the relationship between sense of coherence (SOC) and self-efficacy (SE) based on population data. By conducting an empirical analysis of the two models, we wanted to see whether we could make a valid judgement as to whether both SOC and SE could be utilized in health promotion practice, or whether one is preferable to the other. The study population was randomly selected from the Danish Central Population Register and consisted of five birth-year cohorts (1920, 1930, 1940, 1965 and 1975). The study used the 13-item SOC scale and the general SE scale. The main findings were that SOC score increased by age cohort (p = 0.0004), and there is a positive and graded correlation between SOC and SE (r = 0.39; p < 0.0001) and adjusted OR = 10.3 (CI = 6.7–15.4). We found the strongest association at the lowest level of SOC. For health promotion practice, this finding signifies the importance of focusing on improving SOC in people with a low SOC score, as they are most in need and most likely to increase their SOC level. The finding of higher SOC scores in the older age cohorts indicates that SOC changes over lifetime. Public health work focusing on lifestyle change by increasing SOC can be effective throughout life, however early intervention is important. The finding of a positive correlation between SOC and SE indicates that health promotion altering one of the constructs is paralleled in the other.