Zahir Kanji appeals from a denial of his petition to expunge records. The trial court failed to state the basis of the denial even though Kanji’s petition and accompanying documents satisfied the criteria set forth in section 943.0585, Florida Statutes (2007), and Florida Rule of Criminal Procedure 3.692. We reverse.

In 1991, Kanji was arrested for a felony in Orange County, Florida. The State subsequently filed a Notice of No Information. The Notice recited that “evidence submitted by law enforcement agency insufficient to prove guilt beyond a reasonable doubt.”

In December 2007, Kanji filed his petition seeking to expunge his non-judicial criminal history records and the official court records relating to his arrest. As required by section 943.0585 and Rule 3.692, the petition was accompanied by a certificate of eligibility for expunction issued by Florida Department of Law Enforcement.

The State filed a response in opposition to the petition and requested a hearing. At the hearing, the State presented the trial court with the 1991 arrest affidavits and argued that the public interest would not be served by granting Kanji’s petition. Specifically, the State argued that members of the public who came into contact with Kanji should have unfettered access to his criminal history records so they might be better informed before establishing a relationship with him. The State also observed that the arresting affidavits reflected that Kanji’s purported wrongdoing constituted a “violation of trust” because the alleged victim was a family friend. The trial court took the matter under advisement. Shortly thereafter, the trial,court rendered an order which simply stated: “The Petition to Expunge Records is hereby denied.”

Although section 943.0585 provides that “any request for expunction of a criminal history record may be denied at the sole discretion of the court,” Florida courts have consistently held that such *67discretion is not unfettered. See, e.g., S.L.P. v. State, 949 So.2d 1150 (Fla. 3d DCA 2007); Cole v. State, 941 So.2d 549 (Fla. 1st DCA 2006); Godoy v. State, 845 So.2d 1016 (Fla. 3d DCA 2003); Oymayan v. State, 765 So.2d 812 (Fla. 1st DCA 2000); Anderson v. State, 692 So.2d 250 (Fla. 3d DCA 1997). The words “sole discretion” as used in this section do not permit the arbitrary denial of expunction. Anderson, 692 So.2d at 253. In exercising its discretion, the trial court must consider all the facts and circumstances and may not deny the petition based solely on the nature of the crime. See Cole; Godoy; Oymayan; Anderson.

Here, we are unable to determine if the trial court properly exercised its discretion because no reason was given for the denial of Kanji’s petition. Wells v. State, 807 So.2d 206 (Fla. 5th DCA 2002). Accordingly, we remand the case to the trial court with instructions to either grant Kanji’s petition or provide the reason(s), based on all the facts and circumstances, for denying the petition.

REVERSED and REMANDED.