Increasing attendance to screening offers the best potential for improving the effectiveness of well-established cervical cancer screening programs. Self-sampling at home for human papillomavirus (HPV) testing as an alternative to a clinical sampling can be a useful policy to increase attendance. To determine whether self-sampling improves screening attendance for women who do not regularly attend the Norwegian Cervical Cancer Screening Programme (NCCSP), 800 women aged 25-69 years in the Oslo area who were due to receive a 2nd reminder to attend regular screening were randomly selected and invited to be part of the intervention group. Women in this group received one of two self-sampling devices, Evalyn Brush or Delphi Screener. To attend screening, women in the intervention group had the option of using the self-sampling device (self-sampling subgroup) or visiting their physician for a cervical smear. Self-sampled specimens were split and analyzed for the presence of high-risk (hr) HPV by the CLART® HPV2 test and the digene® Hybrid Capture (HC)2 test. The control group consisted of 2593 women who received a 2nd reminder letter according to the current guidelines of the NCCSP. The attendance rates were 33.4% in the intervention group and 23.2% in the control group, with similar attendance rates for both self-sampling devices. Women in the self-sampling subgroup responded favorably to both self-sampling devices and cited not remembering receiving a call for screening as the most dominant reason for previous non-attendance. Thirty-two of 34 (94.1%) hrHPV-positive women in the self-sampling subgroup attended follow-up. In conclusion, self-sampling increased attendance rates and was feasible and well received. This study lends further support to the proposal that self-sampling may be a valuable alternative for increasing cervical cancer screening coverage in Norway.