OPINION

We must decide whether the Board of Immigration Appeals (“BIA”) erred in dismissing an appeal when the petitioner dutifully followed all regulations and procedures pertaining to filing his Notice of Appeal, but the BIA itself deprived him of the opportunity to timely file his brief by sending the briefing schedule and transcripts of proceedings to the wrong address.

Although the answer to this question seems self-evident, the Immigration and Naturalization Service (“INS”) contends that the BIA’s decision, dismissing petitioner’s appeal from the denial of asylum solely on adverse credibility grounds, should be affirmed despite the BIA’s failure to provide any notice and any opportunity to be heard. Because these minimal due process requirements are clear and fundamental, and petitioner was prejudiced by an adverse credibility determination unsupported by substantial evidence, we grant the petition.

I.

Malkit Singh provides a credible account of persecution on political and religious grounds. Singh fled his native India after suffering persecution due to his support of religious and political rights for the Sikh minority in the Punjab province of India. He entered the United States without inspection in November of 1995 and filed an application for asylum. On September 26, 1996, the INS commenced deportation proceedings against him.

In his asylum application, and during seven subsequent hearings before an Immigration Judge (“IJ”) held over the course of more than four years, Singh described his activism on behalf of the Sikh separatist movement in Punjab, including his membership in the All India Sikh Student Federation (“AISSF”) and his support of the Akali Dal Party.

At the age of nineteen, Singh became involved with the AISSF after an attack on the Sikh Golden Temple, which was believed to be the work of Indian security forces. In 1988, Singh was arrested during an AISSF rally that he organized in Jallhandar. He was held in jail for fifteen days, while being beaten and tortured by the police. He was never charged with a crime nor brought before a judge.

In January of 1992, Indian police again arrested Singh without a warrant. He was held for twenty days, beaten with a bamboo stick, punched, kicked, and threatened with death if he did not end his affiliation with the AISSF. The police told him he was arrested because of his association with Sikh militants, even though he adamantly denied any such association.

In August 1993, Singh was arrested for a third time, along with three other AISSF members, while leaving the Sikh temple in his village. He was held by the police for thirteen days, during which time he was beaten until he lost consciousness. His head was shaved, an affront to Sikh religious practice, and he was then forced to stand for hours under the hot summer sun.

In April 1995, Singh testified that he was arrested for a fourth and final time while distributing party posters and collecting party funds. This time, he was held in jail for thirty-five days, again without being charged with a crime or taken before a judge. While in jail, he was tortured, humiliated, and threatened with death if he continued to support the AISSF.

After Singh’s release, his father arranged for him to leave the country through an agent who secured a fake passport and transportation for him. He traveled via Singapore to Mexico, and then entered the United States.

II.

On December 8, 2000, the IJ denied Singh’s asylum application, finding his testimony internally inconsistent and inconsistent with his application. Singh timely appealed the IJ’s decision to the BIA. He had recently moved to a new address and, following the form’s instructions, he provided his new mailing address on the Notice of Appeal. Accordingly, the BIA sent the receipt for the filing of the appeal to that mailing address. However, on April 24, 2001, nearly a year and a half after Singh filed his appeal, the BIA sent the briefing schedule and transcript of his deportation hearings to his former address.

On July 16, 2001, seven weeks after the deadline contained in the misaddressed briefing schedule had passed, Singh learned of the error and filed an unopposed motion for an extension of time to a file a brief. On April 8, 2002, the BIA denied Singh’s motion as untimely, so he was unable to file a brief.

Six weeks later, over a dissent by Board Member Rosenberg, the BIA dismissed the appeal, stating that Singh failed to provide “any specific and detailed arguments about the contents of his testimony and why he should be deemed a credible witness.” Singh timely petitioned for review.

III.

We have jurisdiction over a final removal order pursuant to 8 U.S.C. § 1252(a)(1). We review for substantial evidence the decision that an alien has not established eligibility for asylum. Cardenas v. INS, 294 F.3d 1062, 1065 (9th Cir. 2002) (citing INS v. Elias-Zacarias, 502 U.S. 478, 481 , 112 S.Ct. 812 , 117 L.Ed.2d 38 (1992)). Adverse credibility findings are also reviewed for substantial evidence. Valderrama v. INS, 260 F.3d 1083, 1085 (9th Cir.2001) (per curiam). We reverse the BIA’s decision “only if the evidence that the petitioner presented was so compelling that no reasonable factfinder could fail to find the requisite fear of persecution.” Singh v. Ashcroft, 301 F.3d 1109, 1111 (9th Cir.2002).

IV.

This is not the typical case in which a petitioner does not receive notice, is deported in absentia, and is before us attempting to explain his (or, as is more usually the case, his attorney’s) failure to appear or to comply with the address requirements, deadlines, or any of the other complex INS regulations. In this case, it is the INS that has been foiled by its own byzantine rules.

The BIA’s refusal to allow Singh to file a brief explaining his allegedly inconsistent testimony violated his right to due process. Indeed, “the BIA must provide a petitioner with a reasonable opportunity to offer an explanation of any perceived inconsistencies that form the basis of a denial of asylum.” Campos-Sanchez v. INS, 164 F.3d 448, 450 (9th Cir.1999); see also Mendoza Manimbao v. Ashcroft, 329 F.3d 655, 660 (9th Cir.2003) (due process satisfied when petitioner has “the opportunity to address the credibility question before the BIA, in briefing and in argument”). Denying Singh the opportunity to file a brief plainly violates this well-established due process right.

The BIA, after sending the briefing schedule and transcript to an incorrect address, justified denying Singh’s motion to file a late brief by asserting that the motion was untimely. However, “[t]o comport with due process requirements, the notice afforded aliens about deportation proceedings must be reasonably calculated to reach them.” Dobrota v. INS, 311 F.3d 1206, 1210 (9th Cir.2002). Notice mailed to an address different from the one Singh provided could not have conceivably been reasonably calculated to reach him. As Singh was not afforded notice of the deadline, the BIA’s reasoning that his motion was untimely is patently insufficient. The INS argues that notice was sent to the proper address, and it is Singh who is at fault for failing to properly inform the BIA of any change of address. However, the very instructions provided on the BIA’s Notice of Appeal form, EOIR-26, require immigrants to file a Change of Address form, EOIR-33, only if they wish to change the address they provided on the Notice of Appeal. The manual the BIA provides to help aliens navigate these treacherous bureaucratic waters clarifies: “When an appeal is filed, the Board relies on the address for the alien that appears in the Notice of Appeal (Form EOIR-26) until such time as a change of address is reported through the filing of a Change of Address form (Form EOIR-33/ BIA).” Board of Immigration Appeals, Practice Manual 16 (2002). True to its word, the BIA at first relied on the address Singh provided pn his Notice of Appeal and sent receipt of the filing there, leaving Singh with no reason to suspect that the BIA was unaware of his current address. In deed, the INS frequently makes Singh’s very argument to us when it sends notice to the address on the Notice of Appeal and either the petitioner has moved without providing a Change of Address form, or he expected notice to be sent to his counsel’s office.

The INS also argues that Singh’s failure to exhaust his administrative remedies robs us of jurisdiction to hear this argument. According to the INS, the BIA requires that a late-filed brief accompany the motion for an extension of time, and Singh “apparently chose not to follow these instructions.” The INS concludes that Singh’s failure to file a brief before the BIA indicates that he has not exhausted his administrative remedies.

As his motion to the BIA and all his briefing in this case reveal, however, Singh had not received the transcript of the IJ proceedings before he moved for an extension of time. We are at a loss as to how Singh could file a brief clarifying the testimony that the IJ deemed inconsistent without having access to the transcript of that very testimony. It is axiomatic that one need not exhaust administrative remedies that would be futile or impossible to exhaust. See Taniguchi v. Schultz, 303 F.3d 950, 957 (9th Cir.2002) (plaintiffs need not exhaust administrative remedies when doing so would be futile) (citing Aleknagik Natives Ltd. v. Andrus, 648 F.2d 496, 500 (9th Cir.1980)).

The BIA did not provide Singh with proper notice of the briefing schedule, nor did the BIA provide Singh the transcript necessary for him to have a meaningful opportunity to “offer an explanation of any perceived inconsistencies [in his testimony].” Campos-Sanchez, 164 F.3d at 450 . Fortunately, on appeal we have access to the briefs Singh would have filed had the BIA used the correct mailing address in the first instance (and to the BIA’s arguments in response). Based on this briefing and argument, we find, as explained below, that the evidence compels a finding that Singh was credible. Because his asylum petition was denied solely on that ground, Singh was prejudiced by the BIA’s failure to give the notice due him.

V.

Section 208(a) of the Immigration and Nationality Act (“INA”) gives the Attorney General discretion to grant political asylum to any alien deemed to be a “refugee” within the meaning of § 101(a)(42)(A) of the INA, 8 U.S.C. § U01(a)(42)(A). See 8 U.S.C. § 1158 (b)(1). “A refugee is defined as an alien unwilling to return to his or her country of origin ‘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.’ ” Fisher v. INS, 79 F.3d 955, 960 (9th Cir.1996) (en banc) (quoting 8 U.S.C. § 1101 (a)(42)(A)). Thus, to be eligible for asylum, an applicant must establish “either past persecution or a well-founded fear of present persecution on account of [a protected ground].” Mejia-Paiz v. INS, 111 F.3d 720 , 723 (9th Cir.1997).

When the BIA determines that testimony describing past persecution is not credible, it must express “a legitimate articulable basis to question the petitioner’s credibility, and must offer a specific, cogent reason for any stated disbelief.” Osorio v. INS, 99 F.3d 928, 931 (9th Cir.1996) (quoting Hartooni v. INS, 21 F.3d 336, 342 (9th Cir.1994)).

After seven hearings, held over the course of more than four years, the BIA boiled down Singh’s testimony to three inconsistencies.

A. Association with Militant Sikhs

The BIA found conflicting testimony regarding Singh’s involvement with “militant” Sikhs. Singh testified that he had no contact or connection with militants. In testimony several months later, Singh stated that militants had once approached him about joining their group, but he declined. He then continued to stress that he had no contact with terrorists. The BIA concluded that his initial denial of any contact was inconsistent with his later admission.

That Singh declined to respond to a militant group’s recruiting effort years earlier is not an admission of anything, and is certainly not inconsistent with stating that he had no connection with militante. Testimony that Singh declined to join a militant group only bolsters his claim that he had .no contact with militants. Moreover, even if we were to agree with the INS that this testimony was inconsistent, any discrepancy “cannot be viewed as [an] attempt[ ] by the applicant to enhance his claims of persecution [and thus has ] no bearing on credibility.” Shah v. INS, 220 F.3d 1062, 1068 (9th Cir.2000). Singh is not claiming that he requires asylum because he was persecuted by militant Sikhs. In fact, he repeatedly testified that the militants never acted unjustly toward him. The BIA failed to follow well-established law when it did not clarify why this purported discrepancy was significant enough to justify an adverse credibility decision. See id; Vilorio-Lopez v. INS, 852 F.2d 1137, 1142 (9th Cir.1988) (“Minor inconsistencies in the record such as discrepancies in dates which reveal nothing about an asylum applicant’s fear for his safety are not an adequate basis for an adverse credibility finding”).

B. Arrest at the Sikh Temple

The next inconsistency cited by the BIA involves the circumstances surrounding Singh’s third arrest. According to the BIA, Singh initially testified that he was arrested for “no apparent reason” after leaving religious services, and yet he later testified that he was arrested with other Akali Dal members after a party meeting. Singh explained, however, that both religious services and meetings occur at the Sikh temple and that on the day in question, he prayed and met with other Sikhs. Furthermore, the source of the BIA’s conclusion that Singh initially testified that he was arrested for “no apparent reason” and later testified it was because of a “party meeting” is unclear. Singh consistently testified that the police never gave him a reason for the arrest and he did not know of one. He never testified that he was arrested because of a “party meeting.” The second hearing was nearly two years after his initial testimony, and he again testified that he had been at the temple for a morning service to “bow his head,” and while the hymns were being sung he was “meeting” other AISSF members.

The fact that Singh did not initially volunteer that he saw other Akali Dal members at the temple is insufficient to support an adverse credibility finding — he may even have found it too obvious to mention. Considering how intertwined the politics and religion of Akali Dal are, it is certainly likely that Sikh separatists would encounter one another at the Sikh temple. Contrary to our precedent, the BIA did not explain why this omission, assuming one exists, is significant or goes to the heart of Singh’s asylum claim. See Singh, 301 F.3d at 1112 (“ ‘[T]he omission of details from an applicant’s earlier testimony cannot serve as the basis for an adverse credibility finding.’” (quoting Osorio, 99 F.3d at 931 )); Shah, 220 F.3d at 1068 (“[W]e will not uphold an adverse credibility finding unless the ... BIA specifically explains the significance of the discrepancy or points to the petitioner’s obvious evasiveness when asked about it”).

C. Disappearance of Khalar

The only remaining inconsistency cited by the BIA relates to the United Nations (“U.N.”) investigation of the disappearance of human rights activist Jawant Singh Khalar. Singh initially testified that, after he had been released from his final arrest, a “neighboring boy” told him that all unjustifiably detained people were released in preparation for the potential U.N. investigation of Khalar’s disappearance. Singh later testified that he did not know exactly when Khalar had disappeared, and he denied saying that his release was a result of the disappearance of Khalar. The BIA therefore concluded that Singh’s initial testimony that he was released because of “international inquiries concerning the disappearance of a prominent Sikh” was incompatible with his denial that his release was related to Khalar’s disappearance.

Again, these two accounts are simply not inconsistent. Singh initially testified that a “neighboring boy” gave him a reason detainees were being released. He never asserted that his own belief was that Kha-lar’s disappearance had anything to do with his release. There is no reason to expect that Singh would know the exact date of Khalar’s disappearance, an event related by a “neighboring boy.” Even if an inconsistency were to exist, the BIA failed to explain how it could go to the heart of Singh’s asylum claim. See Singh, 301 F.3d at 1111-12 . Testifying that he heard a rumor that police released him due to a potential investigation was not an attempt to enhance his claim that he had been arrested on account of his political opinion. Thus this minor difference in narration has “no bearing on credibility.” Shah, 220 F.3d at 1068 .

VI.

Singh’s testimony took place over the course of seven hearings spread out over four years, during some of which he was so fatigued that the hearing had to be continued “in deference to the respondent’s condition.” After reviewing Singh’s testimony alongside his explanatory brief, we conclude that the testimony is remarkably consistent given the circumstances. The BIA’s decision to the contrary is not supported by substantial evidence, and could only be a result of its refusal to entertain Singh’s brief. The BIA’s own words are revealing: it considered its conclusion bolstered by the fact that Singh failed to provide “any specific and detailed arguments about the contents of his testimony and why he should be deemed a credible witness.” Because the BIA denied him the opportunity to do just that, we reverse its determination that Singh is not credible.

Because the adverse credibility decision was the sole basis for the denial of asylum, substantial evidence compels us to find that Singh is eligible for asylum. We therefore remand this matter to the BIA to exercise its discretion, accepting Singh’s testimony as credible, to determine whether to grant asylum.

PETITION GRANTED.

. The Practice Manual is available at http://www.usdqj.gov/eoir/bia/qapracmanual /apptmtn4.htm.