OPINION OF THE COURT
Peters, J.The issue on appeal is whether a portion of New York’s Petroleum Business Tax (hereinafter PBT) violates the Commerce Clause because the statute is an unauthorized exercise of the State’s power over an instrumentality of interstate commerce in that it legislates that vessels1 which merely enter New York waters, propelled by petroleum in their fuel tanks, are deemed to be a “petroleum business” within the State sufficient to establish the requisite nexus for the purpose of taxation even though the fuel consumed during such interstate voyage never comes to rest in the State (see, Tax Law § 300 [b] [1]; § 301 [a] [1]; § 301-a [b], [c] [1] [B]\
*80In June 1998, petitioner Moran Towing Corporation commenced the instant proceeding on its own behalf, and as successor in interest to Moran Towing and Transportation Company, Inc., to overturn a decision of the Department of Taxation and Finance which denied its request for a PET refund. The refund claim was premised upon the assertion that Tax Law § 301-a was unconstitutional under the Commerce Clause (US Const, art I, § 8, cl [3]) because it discriminated, on its face, against interstate commerce. Contending that United States Supreme Court precedent and the Court of Appeals decision in Matter of Tug Buster Bouchard Corp. v Wetzler (89 NY2d 830) supported this challenge, it further asserted that it was not required to exhaust its administrative remedies in the Division of Tax Appeals before pursuing this action.
In November 1998, petitioners Elkof Marine Corporation and Reinauer Transportation Companies, Inc., along with its successor in interest (hereinafter collectively referred to as petitioners), moved to intervene as they too had filed a refund request for all moneys paid pursuant to Tax Law § 301 (a) (1) (ii) and its successor, Tax Law § 301-a (b) (2). Petitioners alleged that the PET was unconstitutional not under the authority of Matter of Tug Buster Bouchard Corp. v Wetzler (supra), but because New York lacked the power to impose the PET on fuel consumed by vessels engaged in interstate commerce by virtue of the United States Supreme Court’s decision in Helson v Kentucky (279 US 245) and its progeny. In an amended answer, respondent denied that the PET was unconstitutional and contended that both petitioners and Moran failed to exhaust their administrative remedies. Supreme Court agreed, further concluding that petitioners had not shown that the statutes were facially unconstitutional. Moran and petitioners appealed.2
Specifically, petitioners assert that the sections under review are facially unconstitutional as each imposes a tax, the levy of which is a transgression of power by New York because (i) it is imposed on a medium or physical manifestation of interstate commerce as opposed to the business or revenue derived therefrom, and (ii) the fuel and the act of consumption during interstate commerce movements never comes to rest in New York and, therefore, neither the fuel nor the act of consumption ever acquires a situs in New York. Respondent contends that the *81challenge to the PBT as facially unconstitutional was laid to rest by this Court’s decision in Matter of Consolidated Rail Corp. v Tax Appeals Tribunal (231 AD2d 140, appeal dismissed 91 NY2d 848) and, thus, petitioners are now required to make their constitutional argument before the Division of Tax Appeals by setting forth the way in which the PBT is unconstitutional as applied to their particular factual circumstances.
It is well settled that a party seeking judicial review of a tax determination must first exhaust his or her administrative remedies (see, Tennessee Gas Pipeline Co. v Urbach, 269 AD2d 19, 21, revd on other grounds 96 NY2d 124). Yet, when the statute is challenged as facially unconstitutional, a basis which is not fact dependent, the development of a factual record at the administrative level serves no purpose and thus constitutes an exception to the exhaustion requirement (see, id., at 21).
We commence our analysis with the fact that vessels are a medium of interstate commerce and remain so even if their activities are conducted within the waters of a particular state so long as the vessel’s presence in such state’s waters is part of an interstate voyage (see, Helson v Kentucky, 279 US 245, 249, supra; Gloucester Ferry Co. v Pennsylvania, 114 US 196, 203-204; Matter of Moran Towing & Transp. Co. v New York State Tax Commn., 72 NY2d 166, 171). As here relevant, between 1984 and August 1990, the PBT imposed an annual tax on vessels3 carrying petroleum products into New York for sale or self-consumption regardless of the situs of the original purchase (see, Tax Law § 301 [a] [1] [ii]) because it deemed such vessels to be engaged in a petroleum business and thus doing business within the State. The PBT was substantially restructured in 1990 to impose a tax for the privilege of doing business in New York based on the number of gallons of fuel sold or consumed by a petroleum business in this State during the month (see, Tax Law § 301-a [c] [1] [B]), yet noted “that no motor fuel shall be included in the measure of the tax unless it shall have previously come to rest within the meaning of federal decisional law interpreting the United States constitution” (Tax Law § 301-a [b] [1]; see, Tax Law § 301-a [c] [1] [B]). However, the Legislature again amended the motor fuel component of the PBT in 1997 by, inter alia, excepting vessels from the requirement that the activity have a substantial nexus with New York before it can be taxed as a “petroleum business” by declaring as follows:
*82“Motor fuel brought into this state in the fuel tank connecting with the engine of a vessel propelled by the use of such motor fuel shall be deemed to constitute a taxable use of motor fuel for the purposes of this subdivision to the extent that the fuel is consumed in the operation of the vessel in this state [with listed exceptions not here applicable]” (Tax Law § 301-a [b] [2] [emphasis supplied]; see, Tax Law § 301-a [c] [1] [B]).
In Complete Auto Tr. v Brady (430 US 274), the United States Supreme Court stated that a tax will be sustained against a Commerce Clause challenge when it “is applied to an activity with a substantial nexus with the taxing State, is fairly apportioned, does not discriminate against interstate commerce, and is fairly related to the services provided by the State” (id., at 279). This Court applied such analysis in Matter of Consolidated Rail Corp. v Tax Appeals Tribunal (231 AD2d 140, supra) where it determined that the petitioner did “not establish [ ] that Tax Law § 301-a offends the Commerce Clause on its face in that the taxed use did not involve goods within the stream of interstate commerce” (id., at 145). There, the petitioner purchased substantial quantities of petroleum fuel from out of State, brought it into New York and stored it until it was used by locomotives engaged in interstate travel (id., at 141). This Court emphasized that while the “ [petitioner was not taxed on any fuel that came into New York in the fuel tanks of its locomotives” (id., at 143), the taxable event triggering the imposition of the PBT occurred “when [the] petitioner withdr[ew] the imported fuel from storage in New York and dispense[d] it by fueling it into locomotives” (id., at 143).
While the “taxable event” necessary for the establishment of the substantial nexus with the taxing state was the “ ‘withdrawal from storage’ of the fuel” in Matter of Consolidated Rail Corp. v Tax Appeals Tribunal (supra, at 144), here petitioners are being taxed as one engaged in a “petroleum business” on fuel purchased outside of New York which is brought into New York in their vessels’ engines and consumed through their intrastate movings while in New York, without having been removed from the stream of interstate commerce and, therefore, never having come to rest, let alone establish a substantial nexus, in this State (see, Quill Corp. v North Dakota, 504 US 298; United Air Lines v Mahin, 410 US 623; Edelman v Boeing *83Air Transp., 289 US 249; Matter of Consolidated Rail Corp. v Tax Appeals Tribunal, supra). While we are mindful that this Court noted in Matter of Consolidated Rail Corp. v Tax Appeals Tribunal (supra), citing to Helson v Kentucky (279 US 245, supra), that tax schemes, such as the PBT, have been upheld in situations where the taxable event is determined to be storage in land-based facilities for future consumption (see also, United Air Lines v Mahin, supra; Edelman v Boeing Air Transp., supra), the challenged statute here facially declares that an activity previously identified as simple inter-' state movement is now, without more, “deemed to constitute a taxable use” (Tax Law § 301-a [b] [2]; see, Tax Law § 301-a [c] [1] [B]) such that a substantial nexus with New York is created.
Since it is fundamental that a substantial nexus with a taxing state must exist before a tax may be imposed under well-established Commerce Clause jurisprudence (see, Quill Corp. v North Dakota, 504 US 298, supra; Complete Auto Tr. v Brady, 430 US 274, supra) (as recognized by the Legislature in its earlier amendment to the PBT where it found that no such fuel “shall be included in the measure of the tax unless it shall have previously come to rest within the meaning of federal decisional law interpreting the United States constitution” [Tax Law § 301-a (b) (1); see, Tax Law § 301-a (c) (1) (B)]), we find the challenged statutes facially unconstitutional.
While we recognize that the United States Supreme Court in Complete Auto Tr. v Brady (supra) set forth a savings analysis to be employed if a statute is found to be facially discriminatory under the Commerce Clause, emphasizing the necessity of gleaning the economic realities, as opposed to the “formal phrasing,” of the challenged statute and that the Court of Appeals followed with a similar analysis in Tennessee Gas Pipeline Co. v Urbach (269 AD2d 19, supra), in both matters there existed no dispute that the activity or business engaged in had a sufficient nexus with the state to justify its imposition of a tax. Here, having found that the challenged statute artificially imposes such nexus — the “means for limiting state burdens on interstate commerce” (Quill Corp. v North Dakota, 504 US 298, 313) — we can find “ ‘ “no set of circumstances * * * under which the [statute] would be valid” ’ ” (Tennessee Gas Pipeline Co. v Urbach, 269 AD2d 19, 21, supra, quoting Matter of Allied-Signal, Inc. v Tax Appeals Tribunal of Dept. of Taxation & Fin., 229 AD2d 759, 763, appeal dismissed 89 NY2d 859, quot*84ing United States v Salerno, 481 US 739, 745). For this reason, no savings analysis need be employed.
Crew III, J. P., Mugglin, Rose and Lahtinen, JJ., concur. Ordered that the judgment is reversed, on the law, with costs, motion denied and it is declared that the New York fuel consumption tax found in Tax Law § 301 (a) (1) (ii) and § 301-a (b) (2) and (c) (1) (B) is unconstitutional.
. Excluded are recreational motor boats and commercial fishing boats.
. Moran has withdrawn its appeal and continues to pursue administrative remedies.
. See, n 1.