Primary headaches are common disease of the modern society and it has high negative impact on the productivity and the life quality of the affected person. Unfortunately, the precise diagnosis of the headache type is hard and usually imprecise, thus methods of headache diagnosis are still the focus of intense research. The paper introduces the problem of the primary headache diagnosis and presents its current taxonomy. The considered problem is simplified into the three class classification task which is solved using advanced machine learning techniques. Experiments, carried out on the large dataset collected by authors, confirmed that computer decision support systems can achieve high recognition accuracy and therefore be a useful tool in an everyday physician practice. This is the starting point for the future research on automation of the primary headache diagnosis.