Krista Paul, Usingmiles.com

Krista Paul came up with a simple solution to a problem that she (and many others) had: using your frequent flyer miles up before they expire. What’s the problem? I don’t know about you, but many of us have several (frequent flyer program affiliations some of us have many!) and sometimes I want to use them but either I don’t have enough on one carrier, or there are blackout days when I want to travel, or whatever – they just don’t all add up together into one usable program! UsingMiles.com solves that problem.

With this free service, travelers can easily search for and book flights and hotels using frequent flyer miles and hotel loyalty points. So, now I can manage all of my flight miles and hotel-rewards points from a single dashboard. In fact, I can now manage all of my loyalty programs in one place, including airlines, hotels, car rental companies, credit cards and retailers. Krista Paul, Usingmiles.com founder and VP of Marketing calls her company “The World’s First Search Engine for Award Travel™.” Usingmiles.com also includes a search engine that helps me optimize my miles and points earned and will even analyze a particular deal to let me know whether I should book with my rewards or cash. “Currently, the site integrates with about 96% of consumer rewards programs,” Krista tells me. And she continues, “And soon we will have 60 additional programs, including hotels, credit cards, car rentals and everything else related to travel, which represents the long tail of travel programs. “ Indeed!

Origins.  But, if this sounds like a simple company solving a simple problem, look again because there is no such thing as a simple startup. Krista went through several company ramifications and a few near-death experiences. Very near death…

She wanted to start a company while she was a student at Boulder. “I was not super entrepreneurial,” Krista tells me. “But I really wanted to do something that was mine, something that I created from scratch. And I really wanted to do something in the travel space because I had traveled a lot.” But she didn’t find a compelling travel idea for a while, so Krista ended up taking a job at Coca Cola in SF.

In SF, Krista started to get restless with her corporate job and wanted to combine travel and social networking into some kind of startup. “My first idea was based on my travels to Australia where they have this great jump-on jump-off bus system. I thought that I could start something like that in the US since we don’t have anything like that.” Krista got a bit of traction with funders and then 9-11 hit, gas prices skyrocketed and she realized that the timing was off. So, she returned the investors’ money and went back to the drawing board.

A year and a half later, Krista came up with the idea of a social networking site that was travel oriented. Her idea was around mapping, but it also entailed her doing a lot of research about frequent flyer miles. The company landed an angel in Colorado, outsourced and off-shored development to India and Krista moved to Colorado. Things were going great with five people on the team and an entry into TechStars, but then a similar site launched and Krista had a revelation: “We got accepted into TechStars but for the wrong idea!” One thing TechStars counsels is that if you are going to fail, then fail fast. At the time, Krista had 25,000 frequent flyer miles that expired unbeknownst to her, and she found in her research that there was no solution that consolidated, organized, and analyzed frequent flyer miles across multiple vendors and then simplified using those miles to travel. “That’s when I knew this was a real opportunity, not just for me, but for hundreds of thousands of people just like me,” she exclaims!

Usingmiles.com is born.  This is now 2008 and the team that went through TechStars came out with a working prototype for the precursor to Usingmiles.com. By then, Krista had worked for free for two years and invested her own money; she was tapped out so she hit Silicon Valley for some additional investment. She found potential investors but then AIG tanked. Second time the economy killed her, or nearly so. She was on death’s door when she met Jon Nordmark, now Usingmiles.com CEO. Jon was the founder and 10-year CEO of eBags.com. Krista explains, “We met Jon, and he told us that our company couldn’t die; the idea was too good. So he stepped in initially as an investor and worked with UsingMiles.com closely for two years. Now he’s the CEO!” Keith Bristol, who led design, usability and eventually global technology services for eBags.com, invested along with Jon; he is now VP of Product Innovation for Usingmiles.com.

Making money.  How does Usingmiles.com make money since the service is free to users? Their business model is multi-faceted Krista tells me: “We get commissions on cash sales. Every time a user makes a purchase, we get a percentage of the transaction. We also get licensing fees and/or revenue shares from existing subscription services run by white label partners.” Advertising is also a future component of Usingmiles.com’s business model, as will be data analytics and premium services.

Usingmiles.com today.  In February, 2011, Usingmiles.com closed on $2.7M in Series A funding by iSherpa Capital. The round included strategic investors such as Navin Dimond, CEO of Stonebridge Companies, which owns and operates over 40 hotels, including Marriott, Hilton and Hyatt. Despite the early missteps, which are so common in entrepreneurship, Usingmiles.com is really starting to make its mark: “We are developing a product that is going to revolutionize the way frequent travelers search for travel,” Krista states proudly and then continues, “At UsingMiles.com we believe that it is nearly impossible for travelers to optimize their loyalty programs when they search for and book travel. There are too many rules and relationships to remember, and the process is too time-consuming. UsingMiles.com will simplify this process by analyzing all of this information for you and delivering you the best travel options based on your loyalty portfolio.”

Krista and her team are launching new features and Usingmiles.com will soon be a meta search engine. She tells me, “Be on the lookout for ways to optimize cash search as well as award travel.” The company plans to launch its mobile app soon too. In addition, Krista hinted that there are several large partnerships on the horizon. I didn’t even ask with whom – she won’t tell me I am sure! Usingmiles.com has been actively hiring “awesome employees and building a great team, but we need java programmers,” she pleads.

Parting words.  Krista has great advice: “This isn’t easy. When I started I was a little naïve. It takes so much longer and you have to make deeper and longer sacrifices than anyone really understands. All my friends are getting married and having kids. Me, I am married to my company. But don’t ever give up. There are super bleak moments, for sure. It’s harder than you ever imagined, but don’t let that prevent you from trying. Even when it seems as though there is nowhere to turn, something inevitably happens and you push through to the other side.”

Ok, Krista, go for it. I am your newest customer!