CANBY, Circuit Judge:

On October 29, 1979, an order to show cause was issued, charging Roman Agmata Baliza with entering the United States with an immigration visa procured on the basis of a fraudulent marriage, in violation of 8 U.S.C. §§ 1182(a)(19), 1251(a)(1) and (a)(2). The order to show cause also charged Baliza with entering the United States for the purpose of performing skilled or unskilled labor without a valid labor certification in violation of 8 U.S.C. §§ 1182(a)(14) and 1251(a)(1). The Immigration Judge found that Baliza was deportable as charged and granted him three months voluntary departure. Baliza appealed to the Board of Immigration Appeals which dismissed his appeal.

On petition for review, Baliza argues that the Immigration Judge’s determination that his marriage was fraudulent was not supported by reasonable, substantial and probative evidence. In addition, he contends that the government’s introduction of his ex-wife’s affidavit deprived him of his statutory and constitutional right to confront and cross-examine the witnesses against him. We find it necessary to address only the latter contention. We hold that the government’s introduction of the affidavit did deprive Baliza of his right to cross-examine witnesses against him. 8 U.S.C. § 1252(b)(3). We therefore reverse and remand for further proceedings.

Baliza is a thirty-four year old male alien. He is a native and citizen of the Philippines. He entered the United States at Honolulu, Hawaii on January 19, 1973. He was admitted as a nonquota immigrant by reason of his marriage on September 18, 1971, to Leonora Valera Borce, a United States citizen. The marriage, which was celebrated at Hocos Norte, Philippines was terminated by divorce on February 22, 1974. Baliza *1233 admitted these facts, as alleged in the order to show cause, at his January 1980 deportation hearing.

Baliza testified that he and Leonora dated for three to five months prior to their marriage and that they married for love. He stated that they decided to get married before Leonora left for the United States, and that Leonora had promised she would bring him to this country. He testified that when he arrived in Honolulu Leonora met him at the airport. He claimed that they lived together at his aunt’s home for three weeks until Leonora ran away with another man. He stated that he filed for the divorce, rather than Leonora, because Leono-ra was told she could not do so while she was pregnant.

In an affidavit dated December 15, 1978, Leonora stated that she was told to marry Baliza and that everything would be arranged for them. She denied ever living with him, before or after the marriage, and stated that she only found out that he had come to Honolulu when his aunt told her he was there. She also stated that she only went through with the marriage because she was very young and her mother and relatives said she should. Neither Leonora nor the investigator who took her statement testified at the deportation hearing. The Immigration Judge admitted the affidavit, which he recognized as hearsay, over the objection of Baliza’s counsel.

The Immigration Judge held that the government met its burden of showing by clear, convincing and unequivocal evidence: (1)that Baliza’s marriage took place less than two years prior to his entry; and (2) that the marriage was judicially terminated within two years after entry. He therefore concluded that Baliza had the burden, under section 1251(c) of coming forward with sufficient evidence to rebut the statutory presumption that his visa was procured on the basis of a fraudulent marriage.

The Immigration Judge noted several inconsistencies in Baliza’s testimony and also considered the affidavit filed by Baliza’s ex-wife. He concluded that Baliza had failed to show by a preponderance of the evidence that the marriage was not entered into in order to evade the immigration laws. He therefore found Baliza deportable under sections 1251(a)(2) and (c).

Baliza’s ex-wife’s affidavit, taken over a year before the deportation hearing, was hearsay. It was an out-of-court statement by a nonparty offered for the truth of the matter asserted. See Fed.R.Evid. 801. As such, it would not be admissible in court unless it could be shown to fall under one of the exceptions to the hearsay rule. Such a showing was not made in this case.

Administrative proceedings are not, however, bound by strict rules of evidence. de Hernandez v. INS, 498 F.2d 919 (9th Cir.1974). Thus the fact that the affidavit was hearsay is not dispositive. In the context of a deportation hearing this court has held that “the only limitation upon its procedure [is] that a hearing, though summary, must be fair.” Navarrette-Navarrette v. Landon, 223 F.2d 234, 237 (9th Cir.1955) (quoting, United States v. Brough, 15 F.2d 377, 379 (2d Cir.1926), cert. denied, 351 U.S. 911, 76 S.Ct. 700, 100 L.Ed. 1446 (1956)). The test is whether the statement is probative and whether its admission was fundamentally fair. Trias-Hernandez v. INS, 528 F.2d 366, 369 (9th Cir.1975); Martin-Mendoza v. INS, 499 F.2d 918, 921 (9th Cir.1974), cert. denied, 420 U.S. 984, 95 S.Ct. 1417, 43 L.Ed.2d 667 (1975).

If credited, the affidavit was probative. It directly contradicted Baliza’s testimony on the crucial issue of the case—the genuineness of his 1971 marriage to Leono-ra. Despite the affidavit’s importance, the government made only a minimal effort at authentication. In his appeal to the Board of Immigration Appeals, Baliza challenged the admission of the affidavit but did not clearly direct his challenge to the lack of authentication. Ordinarily, such an omission might constitute a failure to exhaust administrative remedies that would foreclose further consideration of the affidavit’s authenticity. Chung Young Chew v. Boyd, 309 F.2d 857, 861 (9th Cir.1962). Baliza’s hearsay challenge to the affidavit is suffi- *1234 dent, however, to require us to review the affidavit’s probative value and the fairness of its admission. That review necessarily encompasses some consideration of the affidavit’s authenticity.

The government called no witnesses other than Baliza. The investigator who took the affidavit did not testify. Although the government argues that Baliza conceded that the statement was authentic, the record evidence does not support that claim. Baliza was asked, in reference to the affidavit, “[d]oes the name Roman Agmata Baliza relate to you?” He responded, “[t]hat’s my name.” The government’s attempt to read that ambiguous response as a concession ignores the fact that his counsel objected to the affidavit’s admission, in part because “it wasn’t properly identified.” Thus, although apparently credited by both the Immigration Judge and the Board of Immigration Appeals, the genuineness of the affidavit has never been established.

Even if the affidavit had been authenticated, on the facts of this case its admission raises substantial problems. Congress has required an alien in deportation proceedings to be afforded “a reasonable opportunity ... to cross-examine witnesses presented by the Government.” 8 U.S.C. § 1252(b)(3). The purpose of this statutory guarantee cannot be fulfilled, however, if the government’s choice whether to produce a witness or to use a hearsay statement is wholly unfettered. As noted, the basic issue is whether the affidavit’s admission rendered the proceedings fundamentally unfair. Recognizing the Government’s lack of control over potential witnesses, this court has upheld the admission of hearsay evidence in a number of cases in which the government was unable to produce the witness for cross-examination. See Trias-Hernandez v. INS, 528 F.2d at 370; Martin-Mendoza v. INS, 499 F.2d at 921-22; de Hernandez v. INS, 498 F.2d at 921; Navarrette-Navarrette v. Landon, 223 F.2d at 237. The troubling aspect of this case is the lack of effort the government expended to produce Leonora. No effort was made to locate her immediately before the deportation hearing. During the hearing, the Immigration Judge indicated on January 16, 1980, that the hearing would have to be continued for completion on Friday, January 18. Later on January 16, when he admitted the affidavit over Baliza’s objection, the Immigration Judge stated that the government would make an effort to find Leonora and bring her in on Friday. At the close of testimony on Friday, the Immigration Judge questioned the government attorney regarding the efforts made to locate Leonora. The government responded that it had been unable to locate Leonora and offered into evidence an investigator’s note. That note stated: “No such address as 2101 Wilson Place, occupant at 1124 Auld Lane says subject moved over six months ago. No idea of current whereabouts.” The investigator was not produced to testify as to the extent of his investigation.

The government knew for over a year that Leonora’s testimony would play a key role in its case, yet the record contains no evidence of any attempt to stay in contact with her or obtain her attendance at the hearing. Instead, the government was content to rely on an unauthenticated year old affidavit. An unsigned note, which indicates that in response to the Immigration Judge’s order some effort was made to locate the witness during a twenty-four hour recess, is not enough to justify admission of such hearsay evidence. Admission of the affidavit under these circumstances was fundamentally unfair and consequently deprived Baliza of his right of cross-examination.

The petition for review is granted, the decision and order of the Board of Immigration Appeals is vacated, and the case is remanded to the Board for further proceedings not inconsistent with this opinion.