インターネット異性紹介事業を行おうとする者は、事業を開始しようとする日の前日までに、事業の本拠となる事務所の所在地を管轄する都道府県公安委員会に、所轄警察署長を経由して、届出をしなければなりません。改正出会い系サイト規制法の施行の際(平成20年12月１日）、現にインターネット異性紹介事業を行っている者が、引き続き事業を行う場合には、１ヶ月以内に事業の本拠となる事務所の所在地を管轄する都道府県公安委員会に届出をしなければなりません。
また、インターネット異性紹介事業を廃止したとき、又は届出事項に変更があったときは、廃止等の日から14日以内に、その旨の届出をしなければなりません。
これらの届出はインターネット異性紹介事業を行おうとする者ごとに行います。つまり、インターネット異性紹介事業に該当するサイトを複数開設している場合であっても、当該事業を行う主体が同一である限り、これらの事業をまとめて一つの事業として届出をすることとなります。

　それぞれの届出書の添付書類は、インターネット異性紹介事業を利用して児童を誘引する行為の規制等に関する法律施行規則において定められています。
例えば、インターネット異性紹介事業の開始届出書の添付書類は、届出者が個人である場合は住民票の写し（外国人にあっては、外国人登録原票の写し）、欠格事由に該当しないことを誓約する書面等、届出者が法人である場合は定款、役員に係る住民票の写し等です。

次の1から6までのいずれかに該当する者は、インターネット異性紹介事業を行ってはいけません。

　インターネット異性紹介事業の届出をした者は、自己の名義をもって、他人にインターネット異性紹介事業を行わせてはなりません。