Cancer stage at diagnosis is the most important prognostic factor for survival. We conducted a nationwide, population-based cohort study to investigate cancer stage distribution in immigrants compared to the host population of Norway. All patients recorded in the Cancer Registry of Norway in 1990–2014 were included (17,709 immigrants and 431,936 Norwegians). Individual level sociodemographic data was obtained from Statistics Norway. Ordered logistic regression was used to estimate if immigrants were diagnosed with cancer at a more advanced stage than Norwegians. Seven cancer sites were analyzed (breast, cervix, colorectal, liver, lung and trachea, prostate and stomach). With exception of breast cancer, we did not observe a clear pattern of more advanced cancer stage distribution in immigrants compared to Norwegians. Odds ratios and corresponding 95% confidence intervals for being diagnosed with a more advanced stage of breast cancer for non-Western immigrant groups compared to Norwegians were: Eastern Europe: 1.41 (1.20–1.65), Middle East: 1.58 (1.19–2.10), sub-Saharan Africa: 1.44 (0.99–2.08), South Asia: 1.40 (1.07–1.83) and East Asia: 0.90 (0.72–1.13). Sub-analyses showed that late detection of breast cancer in young non-Western immigrants might be of particular concern. Young (<50 years) non-Western immigrants had an odds ratio of 1.40 (1.21–1.62) for more advanced stage breast cancer compared to young Norwegians.