Bill Me Later went through a few near-death experiences as a start-up in the payment services industry. The company had to revise its business plan before it figured out its real service: performing instant credit checks on Internet users so that they can buy goods online without using a credit card. When someone wants to buy something, Bill Me Later runs a credit check on them. If they are running up bills or they owe Bill Me Later money, it doesn’t approve the credit. Gary Marino, chief executive, kept the operation going for almost eight years and last week managed a big exit. eBay agreed to buy Bill Me Later for $945 million, resulting in one of the best returns for VCs on a deal this year. Here’s his advice on how to survive in a tough market.

VB: How did you get started at Bill Me Later?

GM: I’m not a traditional entrepreneur, but I do like to invent and reinvent. I was helping run a start-up as a consultant. Then a VC from Crosspoint Venture Partners asked me to help. I ran into this company, which was funded by Crosspoint and Nortel. The business model wasn’t that good. I had to convince the VCs at Crosspoint that it would not be very successful. They asked me to stay on and rebuild the company. They had about 90 employees. We started from scratch.

VB: What was wrong with the business model?

GM: It was a model based on calling cards, where they had prefixes that you dialed in and would use it for land-line phones. It would use calling cards as a payment device. You put your number into it with an authorization digit and used phone switches to transmit transactions in addition to phone messages. It was a venture idea backed by Nortel to try to enter the industry for payments. It had significant customer acceptance issues and significant regulatory issues. It was a time when things were moving fast. Nortel just hadn’t done its homework well. I called Jim Dorrian from Crosspoint. We did a very traditional, academic exercise. We looked at the gaps for making payments on the web. We didn’t have a business model. We didn’t have the name. We were talking to the AOL guys about what merchants would want. There was a conversation about magazine subscriptions where the cards had a checkbox item that said, “Yes, I agree. Bill me later.” It was an idle conversation but then our marketing guy’s eyes lit up. He got the trademark for it. So then we had a relationship in place with AOL before we talked to Mike Kwatinetz at Azure Capital Partners. Then 9/11 happened. We had engaged Mike a month earlier. It became a nightmare. We were near insolvency.

VB: What did you have to do to survive? We’re in a tough time again now.

GM: Liquidity comes and goes in the capital markets. You could argue the bust was all about liquidity. Around 9/11, there was a loss of liquidity. We’ve had to survive each of those moments. We have done well with the backing of core investors like Azure Capital, Crosspoint, Kingdon Capital and GRP Partners. We saw a downturn was coming in the fall of last year. We saw the IPO market was closing. We did a mezzanine round, raising a bunch of money from Amazon.com and others. It was more than $100 million. We had T. Rowe Price. It was under the assumption that bad times were coming. That really helped us. We never thought it would get quite as bad as it is now.

VB: How much did you raise altogether?

GM: We raised close to $300 million altogether over the course of seven years. We had been on the road to do an IPO. The last round was meant to grease the skids for the IPO so that it would make the deal more attractive to investors. Instead, we continued to build the company privately.

VB: Did you expect to have to go for [almost eight] years before an exit?

GM: We never expected it before the previous bust. But we have seen a few miracles in our industry such as PayPal. [It takes a long time to change the payment industry]. It was surprisingly long, but we’re proud we made it.]

VB: What was your best break along the way?

GM: Our best break was getting the right investors: Crosspoint, Azure and GRP. If not for the faith that these guys had, we probably would have gone belly up three different times. They thought the business was worth much more and had the right business model. There was a time in 2001, another in 2004 when we were days away from insolvency. And in retrospect, we didn’t know our fundraising in 2007 would be the last.

VB: When did you launch Bill Me Later?

GM: We launched it in 2000 on only AOL. Then we re-engineered it and relaunched it in 2001 with general-purpose merchants.

VB: You saw early on the potential of a web services platform in the form of a payment system that could tap other web services for key consumer data. You could execute multiple web services and then presented the results to the consumer. You were early to discover web services?

GM: It wasn’t one of those epiphanies. We knew that the technology platform was robust in being able to communicate to the point of sale and then gather information from the point of sale. The question was what did we want to communicate and gather? We knew that for instantaneous credit we would have to use lots of bits of data. That’s a short walk to how do you really engage the customer at the point of sale and service them on your web site. Our advisors helped us recognize the platform is much more than an underwriting one and we started to deploy more marketing uses of our platform than just credit uses. It was good strong engineering that let information flow back and forth really well. With that, we could fetch data about a consumer quickly and then send a decision about granting credit back quickly.

VB: When did the service take off?

GM: It started taking off in 2005, after we launched with Wal-Mart. They gave us testimonials. Then we saw significant acceleration in our pipeline of sales. Now we have 1,000 merchants.

VB: I guess consumers had to play catch up and learn to trust this kind of credit check and payment system?

GM: PayPal helped pave the way. We see ourselves the same way. But the equity VC markets were really different for us. It took us a lot longer to get to the same amount of funding and we are now throttling ourselves to a profit target. That’s why this acquisition by eBay will make sense. We just need the capital to get aggressive.

VB: As you reached a certain size, you started contemplating an exit. How long did it take?

GM: We expected a year ago that it would happen rapidly. This is an industry where it’s really hard to do well. We started conversations. In the early part of the summer, we started being more aggressive with the talks. By Sun Valley, at the Allen & Co. conference, it got serious.

VB: You did pretty well in getting a good multiple of sales?

GM: The purchase price was more like seven times sales. It’s really because on a return on investment dollar, our business pays back in 45 days. We found that we wanted to be aggressive but we didn’t have the capital. It didn’t make sense to do an IPO this year, unless you were extraordinarily desperate. We have a lot of pent up demand.

VB: The market jitters affected the price you got of $945 million?

GM: Oh yes. A year ago, they might have paid twice as much. But I’m happy about the outcome. We got the best possible price. I think I had no doubt this was the right thing to do. We knew the market would continue to be scary. I’m not bullish on the markets right now, particularly on the consumer side. Now was the right time.

VB: Do you foresee changes under eBay?

GM: No. I think they know us well. We are good at underwriting, which is more an art than a science. They will let us run our division on our own. They will allow us to access their large merchant and consumer base to bring more revenues into the company.

VB: So we are in the same boat we were in 2001. What kind of advice do you have for entrepreneurs now?

GM: We were flush with cash. You have to believe cash is king and you have to survive on what you have. There is no turnaround around the corner. The markets will move to consumers. My suggestion is tighten up and work close with your partners. There will be casualties. The survivors will those with the best value proposition and the best access to investors with money.