At dawn on April 1, 1945, hundreds of US warships and bombers swept over the island of Okinawa: a hurricane of steel and flame that began the deadliest single battle in World War II’s Pacific theater. A 23-year-old navy officer named Duke Wieden ran ashore with the third wave of troops to tend to the wounded on beaches US forces had code-named Brown 1 and 2. The Okinawans had known them as the village of Irei.

When Duke returned to his ship, he brought back a battered black photo album he had found on the beach. Containing portraits of families, pictures of movie stars, and snapshots of teens, it was a record of happier times in a town his countrymen had annihilated. He was visibly upset as he showed it to his best friend onboard.

A month earlier, Duke’s wife, Violet, had given birth to their first child. He’d never met his son. Maybe he never would. He had lost friends in combat, and it was entirely conceivable that some of the men in these very photos would kill him, too. But something about the album transcended battle lines to evoke visions of the family he hoped to create himself—one not so different from what was documented in these photos. Years later, his war buddy told his family that Duke swore to find the album’s owners and return it, one family to another.

The strength of that moment faded over the months to come, with kamikaze attacks, a typhoon, a second assault on Okinawa. After Duke returned home to Portland, he only let residual anger show in small ways. (He never did like the Japanese Garden.) Even so, he stowed the album in his navy trunk in the basement, and told his family not to open it in his lifetime.

One January morning seven decades later, my phone buzzed with a call from Thomas Lauderdale, the leader of Portland band Pink Martini (for whom I once worked). Lauderdale, an effervescent and connected social catalyst, got me on the phone with Priscilla Wieden, and then her husband, Dan—cofounder of the legendary ad firm Wieden & Kennedy, creator of the Nike slogan “Just Do It,” and son of Duke. The Wiedens had a tale to tell, and they thought it might interest the public radio program This American Life (for which I also once worked).

Shortly after Duke’s death in 2012, his youngest son, Ken, discovered the Okinawa album, its pages damp and moldy, photos stained and falling out. Spearheaded by Duke’s determined second wife, Carolyn, the family had taken up the search for the album’s owner, and after nearly two years of translation, dead ends, new clues, and dumb luck, they had succeeded. Now the Wieden clan planned to head to Okinawa to return it, departing in two days.

Considering time and expense, I suggested they take a recorder and document audio themselves. The ever-optimistic Lauderdale saw no such hurdles. “Priscilla,” he said, “just buy a ticket for someone to go with you.”

Which is how I found myself on the phone the following day with a group of Wieden & Kennedy producers, explaining who the hell I was, what we might need to document the story (Video? Check. Sound guy? We’ll hire one from Tokyo.), and that, should a radio show (or a magazine) want the story, the Wiedens would have no control over the finished product.

Less than 24 hours later, we boarded a Japan-bound plane. Right before the door closed, my phone buzzed again, this time with a text from my stepmother.

“Your granddad invaded and fought in Okinawa.”

I could not have located Okinawa on a map. (It’s closer to Taiwan than to Tokyo.) The island—which maintains its own culture almost 135 years after being conquered by Japan—is probably best known to Americans as the home of Mr. Miyagi from TheKarate Kid and a place where more people live beyond 100 than nearly anywhere else. It’s also base camp for 28,000 US service members—half of America’s forces in Japan—spread across 34 military facilities, a central anchor for our presence in the strategically fraught Asian Pacific. The flight from mainland Japan to Okinawa could have been a post-winter-vacation flight to any US university town: half the plane was headphone-wearing, college-age American kids with duffle bags and cardboard boxes wrapped in tape and twine.

Our small group certainly stood out. Carolyn, Priscilla, Dan, and his sister, Sherrie—decked in the Northwest uniform of puffy jackets and jeans—were trailed by a Wieden videographer with a camera and a beard the size of a dinner plate, and me, with mic and headphones. At the arrival gate, we greeted Erik Lundberg, a gregarious former Portlander who teaches at one of Okinawa’s military bases; his best friend, Jorge Itokazu, a Peruvian-Okinawan sculptor with a penchant for genealogy; and a sound guy from Tokyo whose boom mic hung above all of our heads like a black foam mistletoe.

Random though we looked, our meeting was the culmination of two years of trans-Pacific detective work. After Duke’s son found the mildewed album, Carolyn called her husband’s surviving war buddy and thus learned the story of its discovery on the beach. A self-described “doer,” Carolyn decided to fulfill her late husband’s promise. The night before we boarded the plane, she said, firmly, “I decided: that’s my job.”

Framed by a silver bob, 73-year-old Carolyn Wieden’s eyes are quick to smile and to tear. She carries her own luggage and makes sure everyone else is comfortable before tending to herself. Her already soft, hoarse voice grows even more raw when discussing her late husband. After the war, Duke lived a Portland version of Mad Men’s golden age of advertising, branding Oregon hazelnuts and representing Portland General Electric for decades. Carolyn and Duke married late in life, and she began taping his stories and eventually collected them in a memoir. (His first wife, Violet, died in 1992.) Then she tended him as he lost those memories, one by one, over nine years of dementia, to finally die in 2012.

“There’s nothing like having something you can hold in your hand and remember those people that you love,” she told me in her Irvington living room, where family photographs cover every surface in rows of mismatched frames. “I was sad for the people who didn’t have any of this. I knew we needed to take this album home.”

The first year of her search was an exercise in frustration. She had some of the album’s handwriting translated and found similar names online in Okinawa, but e-mail inquiries went unanswered. She called government officials who agreed to help, but nothing happened. Months passed.

Then a year after Duke’s death, Carolyn got two breaks. She happened to take the album outside, where the bright sun caught a glint of pencil writing on the inside cover, so delicate as to be otherwise invisible. A name and an address: Mitsuko Sunabe of Chatan, Okinawa. Soon after, Carolyn’s guitar teacher met an outgoing stranger at a coffee shop. Erik Lundberg had recently relocated from Portland to Okinawa to teach on a military base. Now she had the owner’s name and boots on the ground.

Lundberg and Itokazu, his ceramicist-genealogist friend, went to the Chatan city offices with their only clue: two team portraits of children in uniforms that read “Irei.” An official there told them Irei had been a small town in the area, wiped out in the war, its land now part of the American base Camp Lester. However, the official added, there was still an Irei community association. He promptly called in one of its nearby members. The blazer-wearing septuagenarian, only a child during the war, flipped through photocopies of the album and stopped on a young man in a military uniform. He recognized the soldier, and took Lundberg and Itokazu to see the man’s younger sister, who in turn recognized herself in a team photo.

“It was one of those very, very cool moments,” Lundberg recalls, “an emotional moment.”

Very soon, a growing chain of Irei connections led the amateur detectives to the album owner’s sister, Iha Sunabe, now 83 and one of the last of her generation. (Original owner Mitsuko, pictured front right in the team photo, died during the war.) “Iha-san believes the album fell into Duke’s hands for a reason,” Lundberg wrote to Carolyn. “When you consider most of the town of Irei was utterly destroyed, there is little that ties the families with their ancestors aside from oral traditions. With Iha-san’s recollection, many others will be affected by the return of the album.”

Carolyn realized she wasn’t returning one family’s memories, but helping restore an entire community’s lost past.

The politics of the twice-conquered Okinawa, once part of an independent island kingdom caught between China and Japan, are complicated, Lundberg explained on the rainy late-night drive from the airport to our hotel in Chatan. Century-old resentments fester toward the Japanese, who annexed the island in 1879. Fresher animosity simmers toward the American military, its outsize influence, and occasional, highly publicized transgressions by US troops. The tensions collide in the ongoing controversy over the military bases: many Okinawans want them reduced, but the Japanese government refuses to relocate them to its mainland islands.

The morning after our arrival, Lisa Tourtelot, a 28-year-old sergeant reporting for the US military newspaper Stars and Stripes, interviewed Carolyn, then joined our curious entourage on a white tour bus. Our guide was a sprightly older Okinawan woman in a polka-dot suit, who manipulated her wrinkled face like a Claymation character to emphasize her points as she described wartime atrocities in ever more animated and almost gleeful detail. Although the Americans were the invaders, the Japanese Imperial Army, as she told it, was to blame for most of the locals’ suffering.

Our first stop was the Prefectural Peace Memorial Museum, which, like most peace museums, chronicles war. The Wiedens wound through rooms filled with empty artillery shells and photographs of starving Okinawans, dead bodies, bomb-shattered buildings, and the otherwise total devastation. As they entered a dark room filled by an enormous diorama of the island and a soundtrack of battle sounds, a video screen lit up. The tour guide explained: “There was rumor going around that the Americas were going to conquer Okinawas. Momma took the baby. Watch carefully.”

In grainy black-and-white footage, a woman approached a cliff’s edge, raised her infant above her head, and cast it off. Then she jumped. The next shot showed bodies littering the rocks below. “They die with honor,” the tour guide intoned, as the sergeant’s camera clicked on the stunned Wiedens.

Lundberg had previously e-mailed Carolyn similar stories told to him by Iha Sunabe. At 15 years old, Iha awoke the morning of April 1, 1945, to a sea crowded with US ships. Her family grabbed as much food as they could and ran for high ground, shrapnel pelting them. When she looked back, her town was gone.

She and her family lived in caves for months. As Japanese forces commandeered what food remained, civilians survived on boiled belt leather from the uniforms of dead soldiers. Japanese authorities told the Okinawans that US soldiers were rapists and cannibals, and issued some families two grenades: one for the enemy, one for themselves. Iha attributes her family’s survival to the fact that they couldn’t find a grenade. (All told, about 150,000 civilians died during the battle for Okinawa.)

“So many times I wanted to say to Miss Iha, ‘Please stop, I don’t want to hear any more,’” Itokazu told me later. His recently deceased father had been a child during the war and had refused to discuss it. “Listening to Miss Iha was like my father talking to me. My soul was feeling like I was being hit by something hard.”

After the museum, we visited a warren of hillside tunnels that housed Japanese naval headquarters. Dan read aloud the final message the Japanese admiral sent to the mainland right before he and his staff committed suicide: “Due to our negligence, these innocent people have lost their homes and property to enemy assault...Even the weeds are burnt. This is how the Okinawa people have fought the war.” We all stooped to walk down the rough-walled tunnels, peering into the small, airless rooms from which the central battle of the Pacific was waged—one imperial power against another, with a small island caught in between.

“I just thought of returning this album as being one family to another,” Carolyn Wieden said. “I wasn’t putting all this into the context of war. I didn’t focus on the fact that they had lost everything. Today we all had to take it in. It’s very brutal to even imagine what they went through.”

I was surprised to find Dan perhaps even more visibly unsettled. His hair and iconic goatee now a professorial silver, Duke’s 67-year-old son has built Wieden & Kennedy into the largest independent advertising agency in the world. Surely someone who unassumingly peppers conversation with anecdotes about shaking hands with Michael Jordan and jokes told to him by Robert Redford—not to mention F-bombs and easy laughter—isn’t fazed by much. Not so.

“I’m a little bit on edge,” he said back at the hotel, his voice halting. “Tomorrow I’m going to meet this family, and what were photographs are going to be real people. I’m not sure how they’re going to react.”