The use of address forms varies from culture to culture according to each society’s sociocultural values and norms. Therefore, the variations in the choice, usage, and understanding of forms of address can create communication problems. This study investigates address forms used in Algerian society between nonacquaintances in different age and gender contexts. It aims to identify the main address categories used to address a stranger and to trace the impact of sociocultural norms and values on their preferences. For this purpose, a discourse-completion task (DCT) was used to collect data from 104 Algerian respondents of different ages and genders which were analysed quantitatively and qualitatively. The results show that Algerians use a variety of address forms with kinship terms dominating, followed by religious terms. They testify that politeness in Algerian society is established by showing deference and respect to elders and at the same time demonstrating intimacy and closeness to the addressee, which is prescribed by the Qur’an. However, the choice of a term is determined by age, power, gender and distance. The findings reflect the collectivist and Islamic nature of Algerian society. The paper provides new insights into the impact of cultural factors on address forms and contributes to address research, cross-cultural pragmatics, intercultural communication and second language teaching.