We present a study of the dimensionality and factorial invariance of religiosity for 26 countries with a Christian heritage, based on the 1998 and 2008 rounds of the International Social Survey Programme (ISSP) Religion survey, using both exploratory and multi-group confirmatory factor analyses. The results of the exploratory factor analysis showed that three factors, common to Christian and religiously unaffiliated respondents, could be extracted from our initially selected items and suggested the testing of four different three-factor models using multi-group confirmatory factor analysis. For the model with the best fit and measurement invariance properties, we labeled the three resulting factors as "Beliefs in afterlife and miracles", "Belief and importance of God" and "Religious involvement." The first factor is measured by four items related to the Supernatural Beliefs Scale (SBS-6); the second by three items related to belief in God and God's perceived roles as a supernatural agent; and the third one by three items with the same structure found in previous cross-cultural analyses of religiosity using the European Values Survey (ESS) and also by belief in God. Unexpectedly, we found that one item, belief in God, cross-loaded on to the second and third factors. We discussed possible interpretations for this finding, together with the potential limitations of the ISSP Religion questionnaire for revealing the structure of religiosity. Our tests of measurement invariance across gender, age, educational degree and religious (un)affiliation led to acceptance of the hypotheses of metric- and scalar-invariance for these groupings (units of analysis). However, in the measurement invariance tests across the countries, the criteria for metric invariance were met for twenty-three countries only, and partial scalar invariance was accepted for fourteen countries only. The present work shows that the exploration of large multinational and cross-cultural datasets for studying the dimensionality and invariance of social constructs (in our case, religiosity) yields useful results for cross-cultural comparisons, but is also limited by the structure of these datasets and the way specific items are coded.