No FIR is  necessary for issuing notice under Section 41A. It can also issued  to a person against a complaint has been made, or credible information has been received or a reasonable suspicion exists.

After lodging of FIR notice is issued under section 41 A of cr PC 

The police officer shall], in all cases where the arrest of a person is not required under the provisions of sub-section (1) of section 41, issue a notice directing the person against whom a reasonable complaint has been made, or credible information has been received, or a reasonable suspicion exists that he has committed a cognizable offence, to appear before him or at such other place as may be specified in the notice.

The individual to whom the Notice is served is obliged to show up at the specified place and time. The individual confirming to the Notice will not be arrested except if in any case considered fit by the Police for which the official is duty-bound to record reasons in writing. Inability to consent to the Notice is a ground for arrest.

It's generally after fir when they need to arrest the accused that issue such notice

- The police officer shall in all cases where the arrest of a person is not required under the provisions of sub-section (1) of section 41, issue a notice directing the person against whom a reasonable complaint has been made, or credible information has been received, or a reasonable suspicion exists that he has committed a cognizable offence, to appear before him or at such other place as may be specified in the notice.

- Further, the person to whom this notice issued shall be the duty of that person to comply with the terms of the notice.

- Further, if that person complies and continues to comply with the notice, he shall not be arrested in respect of the offence referred to in the notice unless, for reasons to be recorded, the police officer is of the opinion that he ought to be arrested.

- Further, if that person fails to comply with the terms of the notice or is unwilling to identify himself, the police officer may, subject to such orders as may have been passed by a competent Court in this behalf, arrest him for the offence mentioned in the notice.

- Hence , the police can issue notice under section 41A to the accused without lodging an FIR ,and lodging of the same is not mandatory. 

Dear Client, 

Police issue notice under Section 41A Cr.P.C. to the accused against whom a reasonable complaint has been made, credible information has been received, or a reasonable suspicion exists that he has committed a cognizable offense, the official can give notice for the equivalent.

Thank You

Lodging of fir is necessary in order to issue a notice.

For issuing such a notice, lodging of an FIR is not mandatory, as evident from Sec 41 A (1).

While the plain wording of  S. 41A appears to suggest an F.I.R. is not necessary for such a notice of appearance to be issued, the matter is not as straightforward. 

The use of the words “reasonable complaint has been made, or credible information has been received, or a reasonable suspicion exists that he has committed a cognizable offence” implies that the police officer is convinced that a cognisable offence has been committed.

The law is clear that the police is under an obligation to register an F.I.R. the moment it is confronted with information that discloses the commission of a cognisance offence (see Lalita Kumari Vs. Govt. of U.P. & Ors., 2014 [1] SCC Criminal). Further there can be no investigation without registration of an F.I.R.

Therefore, how can a police officer who is convinced a cognisance offence has been committed—as evinced by the sending of a S. 41A notice—not register an F.I.R.? They are under an obligation to register an F.I.R. before sending a S. 41A notice.

This point has not been deliberated upon by a court of law yet. It will be interesting to see what a court has to say.

Edit: I must add that in my experience the police usually registers an FIR prior to issuing a notice under S. 41A.

FIR needs to be lodged for issuing notice under Section 41A CrPC.