The plaintiff/appellee, Warehouse Market subleased a commercial building from the defendant Pinnacle Management, Inc. The building is on federally restricted Indian land. Subsequently, the defendant/appellant, Oklahoma Tax Commission (OTC) and the Muscogee (Creek) Nation Office of Tax Commission (Tribe) both sought to collect sales tax from Warehouse Market. Warehouse Market filed an interpleader action in the District Court of Okmulgee County, in an attempt to have the court determine which entity to pay. However, the trial court dismissed the Tribe because it had no jurisdiction over it because of the Tribe’s sovereign immunity. The trial court then determined that the OTC could not be entitled to the sales tax unless and until the dispute between the OTC and the Tribe was resolved in another forum or tribunal. The OTC appealed and we retained the appeal. We hold that because the substance of Warehouse Market’s action/request for relief is a tax protest, exhaustion of administrative remedies is a jurisdictional prerequisite to seeking relief in the trial court.