The four plaintiffs in the U.S. Supreme Court case that overturned California’s same-sex marriage ban tied the knot Friday, just hours after a federal appeals court freed gay couples to obtain marriage licenses in the state for the first time in 4 1/2 years.

State Attorney General Kamala Harris presided at the San Francisco City Hall wedding of Kris Perry and Sandy Stier as hundreds of supporters looked on and cheered. The couple sued to overturn the state’s voter-approved gay marriage ban along with Jeff Katami and Paul Zarrillo, who married at Los Angeles City Hall 90 minutes later with Mayor Antonio Villaraigosa presiding.

“By joining the case against Proposition 8, they represented thousands of couples like themselves in their fight for marriage equality,” Harris, who had asked the appeals court to act swiftly, said during Stier and Perry’s brief ceremony. “Through the ups and downs, the struggles and the triumphs, they came out victorious.”

Harris declared Perry, 48, and Stier, 50, “spouses for life,” but during their vows, the Berkeley couple took each other as “lawfully wedded wife.” One of their twin sons served as ring-bearer.

Although the couples fought for the right to wed for years, their weddings came together in a flurry when a three-judge panel of the 9th U.S. Circuit Court of Appeals issued a brief order Friday afternoon dissolving, “effective immediately,” a stay it had imposed on gay marriages while the lawsuit challenging the ban advanced through the courts.

Sponsors of California’s same-sex marriage ban, known as Proposition 8, called the appeals court’s swift action “outrageous.” Under Supreme Court rules, the losing side in a legal dispute has 25 days to ask the high court to rehear the case, and Proposition 8’s backers had not yet announced whether they would do so.

“The resumption of same-sex marriage this day has been obtained by illegitimate means. If our opponents rejoice in achieving their goal in a dishonorable fashion, they should be ashamed,” said Andy Pugno, general counsel for a coalition of religious conservative groups that sponsored the 2008 ballot measure.

“It remains to be seen whether the fight can go on, but either way, it is a disgraceful day for California,” Pugno said.

The Supreme Court ruled 5-4 Wednesday that Proposition 8’s sponsors lacked authority to challenge the ban after Harris and Gov. Jerry Brown, both Democrats, refused to defend the ban in court.

The decision lets stand a trial judge’s declaration that the ban violates the civil rights of gay Californians and cannot be enforced.

The Supreme Court said earlier this week that it would not finalize its ruling in the Proposition 8 case until after the 25-day period, which ends July 21. But San Francisco City Attorney Dennis Herrera, who joined the two couples in the lawsuit, said Friday that the 9th Circuit panel had the power to lift the stay it imposed.

“The fact of the matter is the only thing holding up the weddings was the stay that the 9th Circuit had in place,” Herrera said. “The fact that there is a separate 25-day period allowing the petition to go for a rehearing is separate and apart from that stay.”

Brown directed California counties to start performing same-sex marriages immediately after the appeals court’s order. A memo from the Department of Public Health said “same-sex marriage is again legal in California” and ordered county clerks to resume issuing marriage licenses to gay couples.

Given that word did not come down from the appeals court until mid-afternoon, most counties were not prepared to stay open late to accommodate potential crowds. The clerks in a few counties announced that they would stay open a few hours later Friday.

A jubilant San Francisco Mayor Ed Lee announced that same-sex couples would be able to marry all weekend in his city, which is hosting its annual gay pride celebration.