NELSON, Circuit Judge, delivered the opinion of the court, in which LIVELY, Senior Circuit Judge, joined. KENNEDY, Circuit Judge (pp. 623-24), delivered a separate dissenting opinion.
DAVID A. NELSON, Circuit Judge.
This matter comes before us on a petition for review of an order in which the Board of Immigration Appeals reversed an immigration judge’s grant of asylum. The Board held that the petitioners were not eligible for asylum because they did not qualify as “refugees.” We conclude as a matter of law that the petitioners did qualify as refugees, and we shall therefore grant the petition for review.
I
The petitioners, Vaso Perkovic and his sister, Djela Perkovic, are Yugoslavian citizens of ethnic Albanian descent. They left Yugoslavia in 1986 and entered the United States without inspection on September 26 of that year. An order to show cause was issued on October 1,1986, charging them with deporta-bility under § 241(a)(2) of the Immigration and Nationality Act, 8 U.S.C. § 1251(a)(2). The Perkovics conceded deportability at their deportation hearing, but requested asylum under § 208(a) of the Immigration and Nationality Act, 8 U.S.C. § 1158(a). They also requested withholding of deportation under § 243(h) of the Act, 8 U.S.C. § 1253(h).
The Perkovics presented evidence that they had been active in a movement promoting civil rights in Yugoslavia for ethnic Albanians. Vaso testified that, while a university student at Titograd, he publicly opposed the government and participated in demonstrations in favor of Albanian civil rights. In Titograd and in his hometown of Luhar, Montenegro,1 he said, he manufactured Albanian national flags and pro-Albanian posters for public display. He secretly posted these signs and flags in public places at night, removing Yugoslav signs and flags. He also helped to organize Albanian students into a group dedicated to the promotion of Albanian civil rights.
[617]*617On November 25, 1985, Vaso testified, he was arrested and taken to the Titograd police station. He said that he was questioned all night by three different shifts of interrogators. Every time he gave a response that the questioner deemed unsatisfactory, he was beaten. By the conclusion of his interrogation, he was unable to walk.
The inquisitors asked him about his political activities with other Albanians, confronting him with Albanian political signs that had been posted around the town. They demanded to know whether Vaso had made and posted the signs. Fearing for his life, Vaso told the questioners that he had not made the signs, although, in fact, he had.
Djela testified that in January of 1986 the police performed a warrantless search of the house in Luhar where she and Vaso lived with their parents. The police found an Albanian flag and cassette recordings of Albanian ethnic music in Djela’s room, whereupon they confiscated these items, arrested Djela, and took her to the police station. She was interrogated overnight and released the next day. She testified that she feared that she would be imprisoned if she returned to Yugoslavia, because the authorities would believe that she had assisted her brother in his political activities.
Vaso was subjected to ongoing surveillance by the Yugoslav police subsequent to his interrogation and beating. In April of 1986 he was again arrested, detained overnight, and beaten. He was questioned on this occasion too about his activities to promote Albanian civil rights, and the authorities made statements that Vaso understood as threats against his life if he continued these activities. Vaso testified that he expected to be imprisoned if he returned to Yugoslavia.
Since their arrival in the United States, according to the petitioners, they have been active in Albanian emigré groups and have engaged in protests against the Yugoslav government’s treatment of ethnic Albanians. Prenk Camaj, an Albanian Catholic priest and one-time Yugoslav refugee, testified that the petitioners had joined his church in Detroit and had been active in promoting Albanian civil rights in Yugoslavia, both before and after their departure from that country. Father Camaj testified that the Yugoslav government actively engaged in suppression of Albanian political and civil rights groups and that it had criminalized a broad range of expression of political opinion and manifestations of Albanian culture.2
Evidence adduced at the deportation hearing further showed that Yugoslav law permitted prosecution of Yugoslav citizens for engaging in political activity outside of Yugoslavia. Expression of political opinions hostile to the Yugoslav government and association with dissident emigré groups were outlawed. A letter from the U.S. Department of State stated that “membership in groups considered by Yugoslav authorities to be hostile to Yugoslavia has been grounds for prosecution of individuals in Yugoslavia.” The State Department also reported that it was likely that the Yugoslav government made an effort to inform itself about the activities of emigrés in the United States, and that it was possible that the Yugoslav government was aware of the petitioners’ political activities in the United States. A State Department report on human rights practices stated that a U.S. citizen of Yugoslav descent had been arrested while visiting Yugoslavia and had been charged with participating in an anti-Yugoslav-government demonstration in Washington, D.C., and with joining “a hostile organization” in Detroit. This “hostile organization” apparently was Father Camaj’s em-igré group.
The petitioners also presented evidence that various members of their family had [618]*618been persecuted by the Yugoslav government over the last forty years for engaging in political activity in support of Albanian civil rights. Three members of the petitioners’ family have been admitted to the United States as refugees in the past.
The immigration judge who presided at the hearing concluded that the petitioners should be granted asylum. Finding the Per-kovics’ testimony credible, he concluded that their promotion of Albanian civil rights constituted “a legitimate expression of political opinion.” Based on their past experiences of surveillance, detention, and physical abuse by the Yugoslav authorities, he further concluded that the petitioners had reasonable grounds to fear that they would be persecuted on account of their political opinions if they returned to Yugoslavia. The immigration judge determined that the granting of passports to the petitioners by the Yugoslav government did not necessitate a finding that they had not been persecuted, nor did the fact that Vaso had been a state-supported student at the University of Titograd. The immigration judge noted that the petitioners “had a comfortable existence in Yugoslavia,” and said that there was no evidence that they had left their native land for economic reasons. Ordering that the petitioners be granted asylum for a period of one year under 8 C.F.R. § 208.10(e) (1987), the immigration judge did not address the Perkovics’ application for withholding of deportation.
The INS appealed the decision of the immigration judge to the Board of Immigration Appeals. In an order dated December 2, 1992, the Board reversed the decision and remanded the ease. The immigration judge subsequently entered an order designating Yugoslavia as the destination of deportation and granting the petitioners the privilege of voluntary departure. The instant petition for review followed.
II
Before considering the merits of the Per-kovics’ petition, we must decide whether we are possessed of jurisdiction over this matter. The INS raised the issue for the first time at oral argument, after which supplemental briefs were received from both sides. The agency contends first that there is no final order for us to review, and, second, that the Perkovics failed to exhaust their administrative remedies.
Only “final orders of deportation” can be brought to this court for judicial review under § 106 of the Immigration and Nationality Act. 8 U.S.C. § 1105a(a). An “order of deportation” becomes “final” upon
“dismissal of an appeal by the Board of Immigration Appeals, upon waiver of appeal, or upon expiration of the time allotted for an appeal when no appeal is taken; or, if such an order is issued by the Board or approved by the Board upon certification, it shall be final as of the date of the Board’s decision.” 8 C.F.R. § 243.1 (1994).
An “order of deportation” includes more than just the piece of paper authorizing the government to take custody of the alien and transport him beyond our frontiers. The term extends to any denial of discretionary relief during a deportation proceeding, where such relief, if granted, would foreclose deportation. Denials of applications for withholding of deportation or for asylum, like denials of applications for suspension of deportation, qualify as “order[s] of deportation” that may be judicially reviewed. INS v. Chadha, 462 U.S. 919, 937-39, 103 S.Ct. 2764, 2777-78, 77 L.Ed.2d 317 (1983); Foti v. INS, 375 U.S. 217, 222-31, 84 S.Ct. 306, 310-15, 11 L.Ed.2d 281 (1963); Carvajal-Munoz v. INS, 743 F.2d 562, 566-67 (7th Cir.1984). The Carvajalr-Mwnoz case, which analyzes in detail Foti and Cheng Fan Kwok v. INS, 392 U.S. 206, 88 S.Ct. 1970, 20 L.Ed.2d 1037 (1968), squarely holds that denial of an asylum application is a reviewable “order of deportation.”
In this ease, each issue presented to us has been the subject of a “final order of deportation.” The immigration judge’s order directing the deportation of the petitioners to Yugoslavia if they stayed beyond the period granted them for voluntary departure is “final,” because the time allotted for an appeal to the Board has expired with no appeal having been taken. See 8 C.F.R. § 243.1. The Board order sustaining the INS appeal from the granting of asylum is likewise final. As “an order issued by the Board,” it was [619]*619“final as of the date of the Board’s decision.” Id. We are aware of no authority for the proposition that a Board order rejecting an asylum application is not a final order unless a formal order of deportation has already been issued.
A slightly more difficult question is posed by the government’s second jurisdictional objection — that the petitioners failed to exhaust their administrative remedies. To recapitulate: the immigration judge granted the Per-kovics’ application for asylum and did not rule on their application for withholding of deportation. The Board then held that the Perkovics were not eligible for asylum. Because the Perkovics had conceded deportability before the immigration judge (by admitting that they were aliens and that they had entered the U.S. without inspection and without a valid visa), all that was left for the immigration judge to do on remand was to enter a new decision designating a country to which the Perkovics would be deported and to rule on any request for voluntary departure. This he did, selecting Yugoslavia as the destination country and granting the petitioners six months in which to leave the United States voluntarily.
The Perkovics did not appeal the new decision to the Board. The INS asserts that failure to perfect another appeal (1) represents a failure to exhaust administrative remedies that (2) bars us from evaluating the legality not only of the ultimate order commanding that the Perkovics be sent back to Yugoslavia, but also of the prior Board order reversing the grant of asylum.
In most contexts, exhaustion of administrative remedies is a prudential, court-created doctrine. Congress, however, has written an exhaustion requirement into the statute establishing federal court jurisdiction over petitions for review of deportation proceedings. 8 U.S.C. § 1105a(c).3 Insofar as a petitioner fails to exhaust his available administrative remedies, therefore, a federal court is without jurisdiction to consider his petition for review.
We conclude that the exhaustion requirement has been satisfied in the case at bar. The issues of deportability and designation of the destination country have been conceded, and the asylum claims have been exhausted because they were presented to the immigration judge and then to the Board, which definitively resolved the claims on their merits.
The fact that the petitioners did not take administrative appeals as to issues not in dispute does not preclude this court from considering contested issues that were properly presented to the immigration judge and then to the Board. Courts of appeals have with some regularity entertained exhausted claims notwithstanding the presence of other, unexhausted, questions. See, e.g., Perez-Rodriguez v. INS, 3 F.3d 1074, 1080 (7th Cir.1993) (two orders, administrative remedies as to one unexhausted; court reviewed exhausted issue on merits); Youssefinia v. INS, 784 F.2d 1254, 1258-59 (5th Cir.1986) (deportability issue unexhausted but asylum issue exhausted; court reviewed order denying asylum on merits); Juarez v. INS, 732 F.2d 58, 60 (6th Cir.1984) (stating that Board order denying motion to reopen is appeal-able, even though remedies as to underlying deportation order unexhausted); Luna-Benalcazar v. INS, 414 F.2d 254, 255-56 (6th Cir.1969) (same).
This practice is supported by the language of the statute, which states that “[a]n order of deportation ... shall not be reviewed ... if the alien has not exhausted the administrative remedies available_” 8 U.S.C. § 1105a(c) (emphasis added). As noted earlier, the category of “order[s] of deportation” includes not just the finding that an alien is deportable and the directive commanding his removal from the country, but also orders denying such relief as asylum and withholding of deportation. In speaking of “an order” (singular, not plural), the statutory lan[620]*620guage focuses the exhaustion analysis on each individual order for which review is sought.
If the petitioners ar t not eligible for asylum or withholding of deportation, it is uncontested that they are deportable. If they are deportable, it is uncontested that Yugoslavia is the country to which they must be returned. It would be pointless to interpret the exhaustion rule as requiring that these uncontested matters be presented to the Board before the Board’s final order denying asylum — an order qualifying, as we have seen, as a final order of deportation — can be considered by this court.
The petitioners were not required to present their asylum claims to the Board a second time. A second administrative appeal on the asylum issues would have been the functional equivalent of a motion for the Board to reconsider its first order. Such motions, as a general rule, need not be filed to exhaust administrative remedies. Wong v. Department of State, 789 F.2d 1380, 1384 (9th Cir. 1986). See also Alleyne v. INS, 879 F.2d 1177, 1180-82 (3d Cir.1989) (petition for review properly before court, even though motion for reconsideration still pending with Board).4 Requiring a motion for reconsideration to be filed in a case such as this one would not only produce a further lengthy delay in the deportation process, contrary to the intent underlying § 1105a, it would punish the petitioners for failing to make a gesture that, in all probability, would have been futile.
Concluding that we have jurisdiction over this petition for review, we proceed to consideration of the merits of the petition.
Ill
A
As we recognized in Dolores v. INS, 772 F.2d 223, 225 (6th Cir.1985), 8 U.S.C. § 1158(a) gives the Attorney General discretion to grant asylum to a “refugee.”5 A refugee is defined as a person who is unable or unwilling to return to his home country “because of persecution or a well-founded fear of persecution on account of race, religion, nationality, membership in a particular social group, or political opinion....” 8 U.S.C. § 1101(a)(42)(A). Disposition of an application for asylum requires a two-step inquiry: first, whether the petitioner is a “refugee” within the meaning of the statute, and second, whether the petitioner merits a favorable exercise of discretion by the Attorney General. INS v. Cardoza-Fonseca, 480 U.S. 421, 428 n. 5, 107 S.Ct. 1207, 1211 n. 5, 94 L.Ed.2d 434 (1987).
The Supreme Court has held that an applicant for asylum has a well-founded fear of persecution if he can show that “persecution is a reasonable possibility” should he be returned to his country of origin. Id. at 440, 107 S.Ct. at 1217. A well-founded fear of persecution has both a subjective and an objective component: an alien must actually fear that he will be persecuted upon return [621]*621to his country, and he must present evidence establishing an “objective situation” under which his fear can be deemed reasonable. Id. at 430-31, 440, 107 S.Ct. at 1212-13, 1217. A well-founded fear of persecution does not require the applicant to show that he probably will be persecuted if he is deported; “[o]ne can certainly have a well-founded fear of an event happening when there is less than a 50% chance of the occurrence taking place.” Id. at 431, 107 S.Ct. at 1213. See also In re Mogharrabi, 19 I. & N. Dee. 439, 445 (BIA 1987) (“an applicant for asylum has established a well-founded fear if he shows that a reasonable person in his circumstances would fear persecution”).
The Board has recognized “the difficulties faced by many aliens in obtaining documentary or other corroborative evidence to support their claims of persecution.” Moghar-rabi, 19 I. & N. Dee. at 445. Therefore, an alien is not required to produce evidence of persecution; the alien’s own testimony can be sufficient to support an application for asylum, “where the testimony is believable, consistent, and sufficiently detailed to provide a plausible and coherent account of the basis for his fear.” Id. See also 8 C.F.R. § 208.13(a) (1994). The Board has held that “[a] well-founded fear ... can be based on what has happened to others who are similarly situated,” and that it is therefore necessary, in considering an applicant’s asylum petition, to weigh evidence of general conditions in the country of origin and the foreign government’s history of treatment of others engaged in similar activities. Mogharrabi, 19 I. & N. Dec. at 446.
An alien has a “well-founded fear of persecution” if:
“(1) the alien possesses a belief or characteristic a persecutor seeks to overcome in others by means of punishment of some sort;
(2) the persecutor is already aware, or could ... become aware, that the alien possesses this belief or characteristic;
(3) the persecutor has the capability of punishing the alien; and
(4) the persecutor has the inclination to punish the alien.” Id.
The Board has held repeatedly that an alien “must ... show that the feared persecution would be on account of his race, religion, nationality, membership in a particular social group, or political opinion,” and that fear of retribution over purely personal matters or fear of general conditions of violence and upheaval do not qualify an alien for asylum. Id. at 447 (emphasis added).
In Cardoza-Fonseca, the Supreme Court explained that the purpose of § 1158, which was added to the Immigration and Nationality Act in 1980, was to bring U.S. immigration law into compliance with international law regarding the treatment of refugees. 480 U.S. at 436-37, 107 S.Ct. at 1215-16. Therefore, according to the Court, it is appropriate to refer to international law on the treatment of refugees in considering the meaning of the asylum provision. Id. at 429, 432-33, 436-41, 449, 107 S.Ct. at 1212, 1213-14, 1215-18, 1222.
B
The main question in this appeal, as we see it, is whether the Board misconstrued the statutory definition of a “refugee.” We conclude that the Board’s construction of the statute in this case was directly contrary both to the manifest intent of Congress in enacting the asylum law and to the Board’s own prior decisions. Under a proper interpretation of the statute, the record compels the conclusion that the Perkovics are “refugees.”
In concluding that the Perkovics did not fear persecution “on account of ... political opinion,” the Board followed a line of cases holding that an alien is not a refugee if his fear of persecution in his home country results only from his commission of common crimes or from the fact that he engaged in violent insurrection against a duly-constituted government. Perlera-Escobar v. Executive Off. for Immig., 894 F.2d 1292 (11th Cir.1990); In re Rodriguez-Majano, 19 I. & N. Dec. 811 (BIA 1988); In re Maldonado-Cruz, 19 I. & N. Dec. 509 (BIA 1988), rev’d, 883 F.2d 788 (9th Cir.1989).
The genesis of the rule applied in these cases is Article 1(F) of the 1951 United Nations Convention Relating to the Status of [622]*622Refugees (incorporated by reference into the 1967 United Nations Protocol Relating to the Status of Refugees, to which the U.S. is a party). Article 1(F) of the Convention excludes from the definition of “refugee”:
“any person with respect to whom there are serious reasons for considering that:
(a) he has committed a crime against peace, a war crime, or a crime against humanity ... [or]
(b) he has committed a serious non-political crime outside the country of refuge prior to his admission to that country as a refugee_” 189 U.N.T.S. 137, art. 1(F) (1951) (emphasis added).
Because a common criminal cannot be a “refugee,” he is ineligible for asylum under § 1158. Similarly, one who commits a “serious non-political crime” in his home country cannot be said, on account of his crime alone, to fear being persecuted because of his political opinion. If he is, say, an armed robber, his government has a legitimate bone to pick with him, regardless of any political views he may hold.
Article 1(F) has no application to the ease at bar. There is no evidence that the petitioners in this case ever participated in any violent actions against the Yugoslav government or ever incited others to do so. There is no evidence that the petitioners ever committed any serious non-political crimes. There is abundant evidence, however, that they committed acts both here and in Yugoslavia that, although protected under international human rights law, are considered political crimes in their homeland.
Yugoslavia outlaws and punishes peaceful expression of dissenting political opinion, the mere possession of Albanian cultural artifacts, the exercise of citizens’ rights to petition their government, and the association of individuals in political groups with objectives of which the government does not approve. Although international law allows sovereign countries to protect themselves from criminals and revolutionaries, it does not permit the prohibition and punishment of peaceful political expression and activity, the very sort of conduct in which the petitioners engaged here. Universal Declaration of Human Rights, U.N.G.A.Res. 217A(III), U.N.Doe. A/810 (1948); Helsinki Final Act, Conf. on Security and Cooperation in Europe, 14 I.L.M. 1292 (1975). The United Nations Protocol on the Status of Refugees specifically speaks to the protection of aliens from punishment for such activities, and the provisions of the Protocol (a binding treaty to which the United States is a party) are deemed to have been incorporated into U.S. law. See Cardoza-Fonseca, 480 U.S. at 486-37, 107 S.Ct. at 1215-16. Since international law and the U.S. asylum statute explicitly seek to shelter activities such as those in which the petitioners engaged, the Board’s construction of the statute to render such conduct outside its scope conflicts with the statute and must be reversed.6
The Board’s decision in this case is inconsistent with the interpretation of the statute reflected in In re Pula, 19 I. & N. Dec. 467 (1987). There the Board granted asylum to a Yugoslav citizen of Albanian descent who had engaged in political activity promoting the civil rights of ethnic Albanians in Yugoslavia similar to the activity engaged in by the petitioners here. As a result of his activities, the petitioner in Pula suffered punishment and harassment similar to that experienced by the petitioners in this case. Notwithstanding the fact that Mr. Pula’s conduct would have violated the same Yugoslav laws cited by the Board in denying the Perkovics’ petitions, the Board held that the petitioner had demonstrated a well-founded fear of persecution on account of political opinion. The Board’s interpretation of the asylum statute in Pula is, we think, irreconcilable with its conclusion in this case. And if the proscription and punishment of peaceful manifestations of political opinion can be dismissed as merely the exercise of a government’s “inherent right” to preserve itself, our nation’s [623]*623asylum laws will have lost much of their intended effect of protecting the exercise of internationally recognized human rights.
Even if the adverse actions taken against the Perkovics by the Yugoslav government were considered as being “on account of ... political opinion,” the Board seems to have thought that such actions still would not give the Perkovics a basis for claiming a “well-founded fear” of persecution. The Board gave no reason for this conclusion, and pointedly ignored the corroborative evidence of large-scale infringements on the human rights of ethnic Albanians and the evidence that Yugoslavia punishes its nationals when they engage in proscribed expressions of political opinion abroad. The Board’s finding in this respect was not based on substantial evidence. Indeed, there appears to be no substantial evidence in the record to support the conclusion that a reasonable person in the petitioners’ position would not have a well-founded fear of being persecuted upon return to Yugoslavia.7
We hold that the Perkovics are “refugees” within the meaning of 8 U.S.C. § 1101(a)(42)(A). The petition for review is therefore GRANTED, the order of the Board of Immigration Appeals dated December 2, 1992, is REVERSED, and the case is REMANDED for further proceedings not inconsistent with this opinion.