Background Female circumcision (FC) has lifelong adverse social and health consequences for women, and its abolition will not only enhance the health of children and women, but also promote gender equality. Like many other Western countries, Norway hosts a large proportion of immigrants from FC-practicing countries, though primarily from Somalia, which is the country with the highest prevalence of FC in the world. A behavioral change by the practicing communities has the best chance to successfully and sustainably eliminate this practice. However, FC prevention programs require a behavioral surveillance that monitors the process of change, with this being the first quantitative study since the major migration of the Somali community to Norway began in 1991 to investigate whether or not Somali immigrants’ attitudes toward the practice has improved in favor of its abandonment. Methods A cross-sectional study using a respondent-driven sampling (RDS) was conducted in Oslo from April to June of 2011. A sample of 214 persons was interviewed, using structured questionnaires. Results The results show that 70% of Somalis in Oslo support the discontinuation of all forms of FC compared to 30% who support its continuation, with the latter group more likely to be people who lived in Norway ≤ 4 years. Of the 10 girls who came to Norway at the age of ≤ 7 years, only one was circumcised, though whether the circumcision occurred before or after the girl’s arrival in Norway remains unclear. The perception that FC is required by religion was the sole factor to be significantly associated with an ongoing support of FC. Conclusion The study reveals that Somalis in Oslo demonstrate a trend to abandon this practice over time. Nevertheless, the 30% of the people who still support its continuation, and who are primarily newly arrived immigrants, require a targeted intervention that is implemented in the early phase of the immigrants’ arrival.