An estimated 35,000 U.S. citizens are living in our country with same-sex foreign partners, but these couples have no right to stay here together on the basis of their relationship. Many of these Americans are faced with a choice between their partners and the country they love. This is true even if the couple is legally married in one of the growing number of U.S. states and foreign countries that recognize same-sex marriage. The Defense of Marriage Act (DOMA), which defines “marriage” for all federal purposes as an exclusively heterosexual institution, stands squarely in their way. Reform options that would help these couples stay together in the United States include a judicial determination that marriage discrimination violates the U.S. Constitution, federal legislation specifically recognizing these couples under U.S. immigration law, and the repeal or striking down of DOMA. This article focuses on the latter possibility. Repealing or striking down DOMA would not necessarily result in a clear, uniform rule recognizing all same-sex marriages under the Immigration and Nationality Act (INA). There is, however, a wealth of guidance about how our immigration system deals with marriages that are recognized in some, but not all, U.S. states. This article maps out the legal terrain that would remain in an immigration world without DOMA. U.S. immigration cases involving marriage validity have been decided in a piecemeal, case-specific manner. A systematic review of the case law, however, reveals that U.S. Attorneys General, the Board of Immigration Appeals (BIA), immigration officials, and most federal courts have consistently applied the same standards to determine marriage validity under the INA. These standards have been employed in dozens of cases involving biracial marriage, marriage between close relatives, marriage involving minors, marriage involving transgender spouses, proxy marriage, polygamy, and even same-sex marriage before DOMA. After distilling and describing a three-step test that embodies the well-established rules for dealing with disputed categories of marriage, this article applies this analysis to same-sex spouses whose marriages are recognized by a U.S. state or a foreign country. It identifies some answers and illuminates possible approaches to a few hard questions that would remain.