There are two ways to get a FBI criminal record check. One is to mail a request to the FBI and receive a criminal record check certificate back by mail. Such an FBI criminal record check must be confirmed by means of an apostille authentication. The other is to submit an application electronically with the FBI or through the FBI approved channellers. This method is faster. The FBI website lists the approved channellers. Please note that criminal record checks from some channellers cannot be opened outside the United States, the services of those channellers can therefore not be used when submitting a criminal record check to the Directorate of Immigration.
In both cases, the applicant needs to be fingerprinted and submit fingerprints with the application. If you are in Iceland, the Reykjavik City Police can take fingerprints.
Please note that if you apply for a FBI criminal record check electronically it is important not to open the document before forwarding it to the Directorate of Immigration. Do not open the link in the e-mail and enter the code. The results can only be opened once. If the document has been opened, the Directorate cannot verify the document and therefore a new check would be required.