Petitioner Stefan Walter Wiedersperg seeks review of an order of the Board of Immigration Appeals (“BIA”) denying his motion to reopen the proceedings which led to his deportation in January 1974. The BIA found against Wiedersperg on dual grounds. The BIA held that it lacked jurisdiction under 8 C.F.R. § 3.2 because Wied-ersperg had already been deported, and held alternatively on the merits that Wied-ersperg had “slept on his rights.” See e.g., Hernandez-Almanza v. United States Dep’t of Justice, 547 F.2d 100, 103 (9th Cir.1976). We grant the petition for review and reverse the BIA’s order.

PROCEDURAL BACKGROUND

In 1968 Wiedersperg was charged in state court with violating former California Health & Safety Code § 11530 for possessing a small amount of marijuana. At the time, Wiedersperg was an alien lawfully admitted to this country. Unaware of possible immigration consequences, Wieders-perg followed the advice of counsel and submitted the issue of guilt to the trial court on the transcript of his preliminary hearing. He was found guilty and sentenced to a fine of one hundred dollars and three years’ probation. The conviction and sentence were affirmed on appeal.

In November 1969, the Immigration and Naturalization Service (“INS”) issued an order to show cause why Wiedersperg should not be deported on the basis of his narcotics conviction pursuant to 8 U.S.C. § 1251(a)(11) . In December 1969, Wied-ersperg was granted an expungement of his state court conviction pursuant to California Penal Code § 1203.4. An Immigration Judge determined that Wiedersperg remained deportable. The BIA affirmed.

On December 20,1973, Wiedersperg filed a petition in San Francisco Superior Court for a writ of error coram nobis, requesting vacation of his conviction on the ground that he had entered his plea in ignorance of the collateral consequence of deportation. The INS granted a stay of deportation pending the outcome of the writ proceeding. On December 24, 1973, the San Francisco Superior Court denied the writ, ruling that the expungement of the conviction had denied it of jurisdiction to grant the requested relief.

Wiedersperg appealed on January 2, 1974. While his appeal was pending, Wied-ersperg was deported to Austria. The California Court of Appeals ruled for Wieders-perg, finding that the trial court had jurisdiction and that Wiedersperg’s allegations, if proved, would have justified the trial court in granting the writ. People v. Wiedersperg, 44 Cal.App.3d 550 , 118 Cal.Rptr. 755 (1975). On remand the superior court granted the petition and issued the writ. As a result, Wiedersperg’s conviction was vacated.

The vacation of his guilty plea left Wied-ersperg facing outstanding charges. His subsequent failure to appear and answer the charges led to the issuance of a bench warrant for his arrest. Wiedersperg was advised by the American Consulate in Vienna that he could not reenter the United States while the warrant was outstanding. Wiedersperg eventually retained counsel in San Francisco who persuaded the district attorney to dismiss the charges and the warrant was withdrawn in October 1981.

On September 15, 1982, Wiedersperg petitioned the BIA to reopen his case on the ground that his deportation had been based on an invalid conviction. The BIA denied Wiedersperg’s petition. He timely appealed to this court. The denial of a motion to reopen is a final order reviewable by this court. Giova v. Rosenberg, 379 U.S. 18 , 85 S.Ct. 156 , 13 L.Ed.2d 90 (1964); Chudshevid v. INS, 641 F.2d 780, 784 (9th Cir.1981).

STANDARD OF REVIEW

Whether a statute or regulation permits jurisdiction over a case is a question of law reviewable de novo by this court. Peter Starr Production Co. v. Twin Continental Films Inc., 783 F.2d 1440, 1442 (9th Cir.1986). The BIA’s denial of Wiedersperg’s petition on the merits is reviewed for abuse of discretion. INS v. Abudu, 485 U.S. 94 , 108 S.Ct. 904, 912 , 99 L.Ed.2d 90 (1988).

JURISDICTION

The BIA found that it had no jurisdiction to consider Wiedersperg’s petition under 8 C.F.R. § 3.2 and 8 U.S.C. § 1105a(c) . Our past decisions require that we reverse. In Mendez v. INS, 563 F.2d 956, 958 (9th Cir.1977), we held that the jurisdictional bars in 8 C.F.R. § 3.2 , and 8 U.S.C. § 1105a(c) to the review of a deportation order that has already been executed apply only where the ‘‘departure” was a “legally executed” one. In that case the government's deportation, without notice to counsel, of an alien whose criminal conviction had been vacated, stripped the deportation proceeding of its legality. The deportation thus could not serve to bar this court from review. Id. at 959.

In Estrada-Rosales v. INS, 645 F.2d 819 (9th Cir.1981), we extended Mendez by holding that a deportation based on an invalid conviction could not be deemed “legally executed.” Id. at 821. In that case the conviction was set aside after the petitioner’s deportation because the magistrate failed to make a record of the plea proceedings as required by Rule 3(c)(2), Rules of Procedure for the Trial of Minor Offenses before the U.S. Magistrates, 18 U.S.C. § 3401 .

The INS argues that the case at bar is distinguishable from Estrada-Rosales on three grounds. First, it contends that, unlike the petitioner in Estrada-Rosales , Wiedersperg “slept on his rights” by waiting three years and eight months after the final order of deportation to file a collateral challenge to his state court conviction, and by waiting over seven years after the granting of his writ of error coram nobis to file his motion to reopen the deportation case. Second, the INS contends that, unlike the petitioner in Estrada-Rosales , Wiedersperg was represented by counsel. Finally, the INS contends that the underlying error in Estrada-Rosales was of constitutional magnitude, while the ground on which Wiedersperg successfully sought post-conviction relief from a California court would have been rejected in a federal court.

The INS argues, in effect, that we should limit Estrada-Rosales to cases where an “alien ... without counsel, suffers a grievous wrong in the criminal proceedings leading to the conviction upon which his deportation is based, and subsequently has that conviction set aside.” (Resp. Brief at 18). In addition relief should only be available where the petitioner has acted quickly to seek relief from the deportation order. Where those conditions are absent, the INS argues, we should apply this court’s decision in Hernandez-Almanza v. United States Dep’t of Justice, 547 F.2d 100 (9th Cir.1976). In that case we affirmed a BIA decision refusing to reopen deportation proceedings for an alien who returned to the United States illegally and successfully attacked his state court conviction only after new deportation proceedings had begun against him.

We cannot agree that these distinctions go to the essential holding of Estrada-Rosales . There we placed the primary emphasis on the fact that the conviction which supported the original deportation decision had been vacated.

Estrada-Rosales, 645 F.2d at 821 .

We also pointed out that the conviction was “a key part of the government’s case in the deportation proceeding.” Id. That conviction having been overturned on the merits, “[petitioner in these circumstances is entitled to a new deportation hearing.” Id. Here, Wiedersperg’s conviction was the sole ground of his deportation, and that conviction is itself erased and cannot serve to establish that he has committed a crime. He stands neither convicted nor charged with the crime for which he was deported. Estrada-Rosales applies.

Nor do we think that delay in seeking relief was the foundation of our decision in Hernandez-Almanza . There the petitioner did not attack the conviction underlying his previous deportation until new deportation proceedings had been initiated. In the meantime he had re-entered the country illegally. Wiedersperg, on the other hand, has proceeded lawfully. Moreover, as we indicate below, much of his delay is attributable to the difficulties of accomplishing from a distance the various steps that ultimately cleared his record. He should not be ineligible for relief on that ground.

Finally, we cannot agree that Estrada-Rosales is limited to infirmities in the underlying conviction that would be grounds for federal relief. In Estrada-Rosales , the petitioner’s deportation was based on a violation of federal law, and consequently the only relief available was federal. Here Wiedersperg’s state law conviction was the ground of deportability and state law properly applies to the validity of the conviction. Where Congress has made deporta-bility depend upon a state’s action in convicting an alien of a state-defined crime, it offends no sense of symmetry to hold that a state’s action vacating and totally nullifying that conviction should render the deportation not legally executed.

DENIAL ON THE MERITS OF WIED-ERSPERG’S MOTION TO REOPEN

The BIA also denied Wiedersperg’s motion to reopen on the merits, finding that he had waited such a long time that the prosecution was effectively crippled in its ability to bring a new case against him following the reversal of his conviction. Deliberate manipulation of post-conviction procedure to nullify any opportunity for retrial may well be a ground for denying a petition to reopen, but we cannot agree that the INS claims here have risen beyond the purely speculative. The facts are far from clear that Wiedersperg deliberately or negligently delayed in pursuing his appeal. He filed his writ of error coram nobis prior to deportation and managed to continue the appeal after he was deported to Austria.

To justify reopening a deportation proceeding, an alien must make a prima facie showing that he or she is eligible for relief. Sakhavat v. INS, 796 F.2d 1201, 1203 (9th Cir.1986). This and other courts have clearly established that the nullification of a conviction upon which deportability is premised deprives deportation of a legal basis. See Hernandez-Almanza v. United States Dep’t of Justice, 547 F.2d 100, 103 (9th Cir.1976); Zinnanti v. INS, 651 F.2d 420, 421 (5th Cir. Unit A July 1981); Aguilera-Enriquez v. INS, 516 F.2d 565, 570-71 (6th Cir.1975), cert. denied, 423 U.S. 1050, 96 S.Ct. 776 , 46 L.Ed.2d 638 (1976).

Both this court and the Supreme Court have held that where the legal basis of a finding of deportability has been nullified, a new deportation hearing is warranted. Bridges v. Wixon, 326 U.S. 135, 156 , 65 S.Ct. 1443, 1453 , 89 L.Ed. 2103 (1945); Kovac v. INS, 407 F.2d 102, 107 (9th Cir.1969); Estrada-Rosales v. INS, 645 F.2d 819, 821 (9th Cir.1981). Wiedersperg’s successful overturning of his state conviction establishes a prima facie showing for relief. We hold that it was an abuse of discretion for the BIA to deny Wiedersperg a reopened hearing on the speculative grounds that he had “slept on his rights” in such a way as to prevent his retrial.

CONCLUSION

The petition for review is granted. We REVERSE the BIA’s denial of Wieders-perg’s motion to reopen and REMAND the case to the BIA to reopen Wiedersperg’s deportation proceedings.

POOLE, Circuit Judge, dissents and may file a separate opinion later.

. 8 U.S.C. § 1251 (a)(ll) provides in part: [a] Any alien in the United States ... shall, upon the order of the Attorney General, be deported who (11) ... has been convicted of a violation of, or a conspiracy to violate, any law or regulation of a State, the United States, or a foreign country relating to a controlled substance (as defined in section 102 of the Controlled Substances Act ( 21 U.S.C. § 802 )). . 8 C.F.R. § 3.2 provides in part: A motion to reopen or a motion to reconsider shall not be made by or in behalf of a person who is the subject of deportation proceedings subsequent to his departure from the United States. This regulation takes its language from and operates parallel to 8 U.S.C. § 1105a(c) which provides in part: An order of deportation or exclusion shall not be reviewed by any court if the alien has not exhausted the administrative remedies available to him as of right under the immigration laws and regulations or if he has departed from the United States after the issuance of the order.