Tell us a bit about how you came to found your first business.

So I joined a little tiny startup called App Media in 2003. I actually ran business development so I was cold-calling sites, which is actually pretty funny — calling MenuPages.com and [saying] “Hey, you should use us for advertising,” [and] the guy at MenuPages was like, “Why? Why would I ever talk to you, who are you?” You learn a lot when you cold call people, and one of the things I learned was that the technology they were using to choose ad networks wasn’t very good.

So in the summer of 2004 I decided to build a very simple ad management platform for publishers that would let them choose which network made the most sense to send ads to. And that was a miserable failure because I was trying to charge 10 percent of the publishers’ revenue. And it was just too much to get them to commit to. I bumped into a guy who at that time was at a little Israeli ad network who said “I heard you guys have great technology, can we license your [product] for our ad network in Israel? In an ad network, at least at that time, you are only as good as your technology. The idea of licensing our technology to a competitor was somewhere between anathema and sacrilege.

But I went back to the office and I thought about it, and I thought hey, as an ad network we have a few hundred publishers in our network. There’s a million [publishers] globally, [it could] take us decades to get every publisher to use us as a network —what if we went to all the networks and [got] them to use our technology? So I spent two months locked in a dark closet with two other engineers building a new version of the platform for networks, [and] we got back to New York and we start trying to roll it out and it was so successful not because the software was good —it was good — but because there was a feature we built that would let us let a network using the platform buy and sell impressions from the other networks. And this was a brand new concept, we didn’t know what to call it at that time, but a year later someone came up with the term “advertising exchange.”

And at what point did your co-founder Mike Nolet become involved?

Mike called me in 2005. We both went to Princeton, I was [there] many years before he went there — he saw my name in the alumni directory, I guess he was searching for people who were entrepreneurs, and he was just cold emailing them and saying “Hey, can I talk to you about how you got where you are?” And I took his call and said “Look, I don’t do informational interviews, either interview or go find someone else.” He interviewed and he got a job and he was extraordinary. He was clearly one of those people who was just so talented that you know anything they do is going to be hugely successful, and so by the time we sold Right Media to Yahoo! it was evident that he was something special.

I got fired from Right Media because I had some conflicts with the CEO around the future of the company. I wanted to take the exchange concept to the next level, and the CEO didn’t really want to make those investments. And in hindsight he was right: Yahoo! bought the company as it was for a heck of a lot of money and it probably would have been crazy to swing for the fences the way I was proposing. After that conflict, he fired me, and I was determined to go do the “swing for the fences” idea, which became AppNexus. And the one smart thing I did, perhaps the smartest thing I did when I got fired, they gave me a one year non-compete and a one-year no hire and I said, “I will do a no hire, but it has to exclude Mike Nolet, I won’t hire anybody except Mike.” They said okay, and they walked to Mike’s desk and said, “We’ll pay you a million dollars to stay for a year and not join Brian’s company.” And so Mike being a very smart man, said okay, waited 3 months for his first quarter million dollar check — the next day, I kid you not, the next day we started AppNexus together. So our startup capital came from the sale of Right Media and Mike’s first check from [Yahoo!].

[UPDATE: As of 10/8/13, Mike Nolet announced via the company's blog that he will be stepping down as CTO of AppNexus and transitioning to an advisory role in order to focus on other projects, including starting a new online business.]

And how did you come up with the idea for AppNexus?

[Mike and I] came up with this idea that the biggest problem we had at Right Media over time was getting more hardware to keep up with our hyper-growth, and so we were watching what Amazon had done with their competing platform, Amazon Media, and we thought “Gee, it would be really cool if someone built the equivalent of Amazon’s cloud for real time advertising.” And we called Amazon and said, “Can we use your cloud for this?” And we told them the technical requirement, and they said, “That’s crazy,” and we said, “Okay, this sounds like a business idea.” And so we flew out to the West Coast, pitched some investors, and that was the genesis of the business and how Mike came to join me.

What was the decision-making process like that led you to pursue outside investment?

Building a cloud business just requires capital, there’s no way around it. So once we decided that’s the business, it was pretty much inevitable that we’d have to raise money. In terms of raising money, the best way to raise money is to have just sold your startup for hundreds of millions of dollars. I strongly recommend selling your company for hundreds of millions first. On the other hand, pissing off your boss who is now a senior executive at Yahoo!, such that he has to fire you, doesn’t help you raise money.

What ended up happening was I met this guy named Ron Conway at a barbeque or something. Ron Conway is the [godfather] of angel investing. He’s invested in hundreds of companies, Google, and every big name company that has come out of the valley. I called him up and I sort of pitched him on this cloud computing idea, and he said “Look, I don’t know a whole lot about this but you know who you should talk to is Marc Andreessen — he did LoudCloud back in the early 2000s, [which was both] a huge success and a huge failure, and he will talk you out of this business — he will tell you why you’re crazy to start a cloud computing company, just wear a helmet when you talk to him. It’s gonna be ugly.”

So I met Marc Andreessen, and in this room happens to be the CEO of Usware [who was] also the CEO of LoudCloud at the time, and so the two of them listened to me explain the idea and they gave me incredible feedback, and they said “You know, this is a slog, if you want to be in the enterprise hardware or the enterprise software space it’s going to be a slog.” And that was actually really helpful advice, you know, because having just come off of a great exit it was sort of sobering. And you know, I got up to walk out of the room and they said, “Oh by the way, can we invest?”

And I said “Yes of course!”

And of course once those guys invested, everyone in the Valley wanted to invest. So the Series A was easy. The problem was six months later, we had launched the cloud business, we scaled it up, we were on a two or three million dollar a year run rate in four months, which is sort of amazing, but Amazon and a couple other players were being incredibly aggressive, and it was pretty clear that Amazon was watching us and in hindsight going out and meeting them may not have been the best idea. They were adding back all the features that they told us they wouldn’t provide.

And so less than five months after raising money and running very quickly towards being out of money I called the investor group and said look, we’re going to pivot, when our non-compete ends in July we’re going to pivot to being an ad business: we’re going to recapitalize the company so that we can go take our cloud and turn it into an advertising business.

The problem was now I had to go back and raise more money, [and investors kept saying] “Okay, you just raised money six months ago and you’re raising again. And you decided you didn’t want to do cloud space. And you want to be in the ad space, but you can’t tell me what you’re going to do because of your non-compete. Why would we invest now?”

And I was like “Well, because I’ll be out of money by then.” So I flew back and forth to Boston, like, ten times and got rejected by everyone, I flew out to the Valley and got rejected — I mean just total and complete rejection. And the non-compete ended, and still everyone was like “Well, we know you’ve been raising money for a few months, [and] no one has funded you, therefore it doesn’t seem like a good business.”

By August I was desperate and an advertising company [in Los Angeles] offered to buy AppNexus for $ 30 million, [and we seriously considered it]. And I just made a couple more phone calls to people trying to get them to invest, a guy up in Boston called Mike Carroll took a meeting with me, and I don’t know what was different than him than everyone else, [but his feeling was that I] clearly have the ability to launch new businesses and [he didn’t] understand why people [weren’t] investing, so [he was] just going to invest. And as soon as he said he was going to invest we got two other term seeds within two weeks, just to give you an example of how these things behave.

My favorite story about that, that Howard [Lerman, Yext CEO] likes to tell is that [initially when] raising money I would put a suit on by the time August came around I was so depressed that I stopped wearing suits, and I was like screw it, I’m just gonna dress in shorts and a T-shirt because I just can’t be bothered, and so all of those term sheets that I got in August came from me not wearing a suit. My close rate with a suit on was 0 for 40 and my close rate wearing my regular clothes was like 3 for 5. Maybe my suits are just really ugly, I don’t know.

Where do you see the industry going in the next few years?

Well, I think mobile, meaning phones and tablets especially, is gonna completely change as we understand it. Let me you a simple example of that: for the past 15 years the Internet portal has been the dominant way that people access content. You know, back in 1995 I would go to Yahoo!, which was grey with blue links, and I would navigate around looking for something cool to check out. And today Yahoo! has a much more diverse set of properties, and something will link me to another Yahoo! property, and so forth. There is very much this conjoinment and that’s why they can acquire a content property like Tumblr and tie them in, because the idea is that people on Tumblr will then consume more Yahoo! properties and services. On [a mobile] phone, the apps are actually distinct. So when I go into the Yelp app, I search for a restaurant and then I leave the Yelp app and go to a different app that serves a different purpose. Now, it’s possible that Yelp could have a number of different apps, and they [would] say, “Hey, you should install this other app.” But in the mobile world the portal is the phone itself, so I have folders on my phone of the different kinds of things I do on my phone, and it actually changes the way content is consumed which means fragmentation for advertisers.

There’s not going to be, I suspect, the same consolidation [in the mobile world as there was on the internet proper]. Facebook will still be extremely powerful; Google will be powerful. But I think the world in 2003 where ad networks really mattered a lot is [shifting to mobile]. And networks matter not because there’s something implicit in the networks themselves, but because of the content fragmentation [on mobile meaning] that you need someone to effectively sort through all of the noise and think about ways to deliver consistent advertising experiences across a number of different apps. We announced a couple of weeks ago a partnership with Millenial Media, which is the largest mobile ad network and the thesis behind that is that networks are incredibly important.

I think that the idea of providing a consolidated technology platform and monetization proposition for mobile is critical and if we can bring all the technology we have built to bear [on it], then we have the ability to actually significantly impact how mobile works. So to me that’s the next couple years of the industry, and many players haven’t recognized this yet and haven’t put apps on the table to do that. We spent the last year on an all-in effort to be a leader in the mobile space, and so what I hope is in two years you hear a lot about how AppNexus is changing the fundamental economics of mobile content and mobile advertising.

This interview has been edited and condensed.

Betabeat