A 25 Bitcoin token © Rick Bowmer, AP

"In bitcoin," Austin Craig repeated to the young woman behind the counter at the Lean Crust Pizza parlor in the Fort Greene neighborhood of Brooklyn, N.Y. "Can we pay in bitcoin?"

"In what?" came the reply.

Craig, 30 years old, was struggling to convince Nadia Alamgir of the existence of the virtual currency that has gained traction across the world, and whose value -- after months of wild swings -- recently reached records around $400 per bitcoin.

It was midway through a tricontinental odyssey taken with his wife, Beccy Bingham-Craig, 29, and a film crew documenting their travails, which started in Provo, Utah. Their mission: to live on bitcoin alone.

"It's been consistently inconvenient and occasionally frustrating," Craig said outside Lean Crust, "but never impossible." Lean Crust advertised itself as bitcoin-friendly but hadn't seen much virtual foot traffic. Alamgir eventually contacted the store's owner, who arrived and processed the transaction, allowing Craig to munch on several slices.

Lean Crust, though, is one of a tiny but growing number of stores, travel agents and online merchants starting to accept the once-obscure digital currency as a means of payment. Bitcoin doesn't exist, except in the virtual world, and can only be passed from one person to another electronically. Its origins are murky: Conventional wisdom says a man or group of people going by the name Satoshi Nakamoto created bitcoin in 2009, stoking demand by making it obtainable only through complicated algorithmic searches by powerful computers.

But in the past 12 months, the bitcoin zeitgeist has taken on a life of its own. The currency is discussed at investing conferences now. The Winklevoss twins, known for their fight with Facebook founder Mark Zuckerberg, have started a bitcoin fund. It also has gained the attention of regulators who worry it can be used to launder money.

For the Craigs, bitcoin represented a chance at adventure -- and an underground movie career.

They began their trek in October by driving east from Provo in Bingham-Craig's 2004 Volkswagen Jetta. After arriving in New York on Oct. 17, they flew to Stockholm, Berlin and Singapore before eventually returning to Provo. In the end, they lasted 101 days, from July 23 to Nov. 1.

The Craigs weren't part of the bitcoin underground when they began the project. Craig said he first heard of the currency in 2011 and then came up with the plan to live and travel solely on bitcoin.

"I'm really excited about bitcoin and its future," Craig said. "It's a reimagining of money."

Starting July 23, the day they returned from their honeymoon, the Craigs paid for everything with bitcoin, from rent to food to gas. At that time, one bitcoin was worth about $98, based on trading at the Tokyo-based Mt. Gox exchange, a primary exchange bitcoin enthusiasts have tracked.

During the trip, they had to not only introduce a number of people to the fledging currency but to persuade them to use it. After a few weeks of prodding, their landlord, Justin James, agreed to the plan -- with the sweetener of a small premium over the rent -- and set up his own bitcoin account.

"In the end," James said, "it hasn't been as much of an inconvenience as I thought it would be." While he hasn't become a convert, he did say he thought the experiment sounded like fun and was "happy to be a part of it."

After scouring Provo, they found one grocery store, LoLo's Fresh Food Warehouse, that would accept the currency. They found one auto insurance company that would take bitcoin. The single hardest thing to get regularly, Craig said, was finding gasoline. Early on, they hardly drove their car.

"For the first two weeks" of the experiment, Craig said, "we had no place to fill up."

They were saved by Jeremy Furbish, a bitcoin enthusiast they knew only as "Furb," who works the night shift at a Phillips 66 station outside Salt Lake City. He heard about their story and contacted them. "Driving an hour out there on a Friday night at 10 became part of our routine," Bingham-Craig said.

Furbish has tried in his own way to preach the gospel according to bitcoin -- sometimes pricing items at the store in both dollars and bitcoin -- but what the Craigs did far exceeded his modest efforts, he said. "The best that I have been able to do is to get a bunch of Boy Scouts to accept bitcoin as payment for mowing my ex-wife's lawn," he said.

Craig's employer agreed to pay him in bitcoin. The couple found travel agencies in Germany that accepted bitcoin and, through them, arranged their hotels and flights for the world tour. They drove Bingham-Craig's car, with the film crew following in a car rented with bitcoin from Five Star Auto Direct in Orem, Utah, which also helped sponsor the film. They drove from Provo to Denver, Kansas City, Chicago, Pittsburgh and New York.

The car was stocked with food and other supplies -- like four five-gallon gas tanks, which were covered under a tarp to fight the fumes and were carried in case the couple couldn't find a gas station.

"We didn't want to end up starving and destitute in a ditch," Craig said.

With help from the two German travel agencies, SimplyTravelOnline.com and 9flats, they booked flights and hotels.

In New York, they ate pizza. In Stockholm, they went hungry the first night. In Singapore, Binghman-Craig got a henna tattoo. At every stop, Craig said, they found at least one bitcoiner willing to help.

"We didn't know how much the duration of it would wear us down," Craig said. "Totally average things became monumental challenges."

In the end, despite skepticism from friends, family and the bitcoin community itself, the Craigs managed to live on bitcoin for over three months. "We really didn't cheat," Craig said. "Everybody thought we would."

And as for Almagir of the pizza joint, she has become a convert.

"I'm a fan of bitcoin now," she said, adding she was considering buying some herself.

Click here to become a fan of MSN Money on Facebook

More from The Wall Street Journal: