The Motley Fool is on the road in Seattle! Recently we visited Coinstar -- now officially renamed Outerwall (OUTR) -- to speak with CFO-turned-CEO Scott Di Valerio about the 22-year-old company's well-known coin-cashing machines, as well as its more recent acquisition of Redbox, and future initiatives to expand into other aspects of the automated retail market.

In this interview, Scott chats with The Fool about the economics of coin and video kiosks, Coinstar's share repurchase program, and its exciting initiatives in a number of new automated retail spaces as well as related online services. From coffee and breakfast to cosmetics and photo shoots, Coinstar is looking to move into much more than coins and video.

A full transcript follows the video.

The retail space is in the midst of the biggest paradigm shift since mail order took off at the turn of last century. Only those most forward-looking and capable companies will survive, and they'll handsomely reward those investors who understand the landscape. You can read about the 3 Companies Ready to Rule Retail in The Motley Fool's special report. Uncovering these top picks is free today; just click here to read more.

Austin Smith: Scott, thanks so much for joining us today.

Scott Di Valerio: Thanks, I appreciate you being here.

Austin: Thanks for having us.

Newly in the CEO role, came up from the CFO ranks -- I'm wondering if you could maybe talk a little bit about that transition and what it's like now that you're steering the ship?

Di Valerio: Yeah. It's been a lot of fun. I've been on the team for three-and-a-half years, so really working hard to set the strategy with our executive team and coming in as the CEO, working with that team to continue to push forward.

The good thing is we have a good, strong strategy that's leveraging our leadership in automated retail. We're focusing across six sectors that we set up. That gives us about a $16 billion revenue sweet spot for us in the automated retail space, in an $85 billion market.

We're really setting course with our team to be able to get after that part of the business.

Austin: When you say $85 billion, is that what you see as the addressable market for automated retail?

Di Valerio: For automated retail, yes. Then when we narrow it down to the six sectors that we're looking at and the sweet spots that we think we can get after, it's around $16 billion. With some adjacencies around it, it'll go out to around $20 billion, so we've got a nice, big market for us to get after, and being a leader will allow us to get after it pretty quickly.

Austin: Nice to have those good runways.

Di Valerio: That's right.

Austin: You said you were looking at all these markets. If you look five years out in all of your adjacent markets, where do you see automated retail five years from today, both from your perspective, and from an industry perspective?

Di Valerio: I think automated retail really plays into the trends that we're seeing here -- urbanization, the 24/7 gratification that people want -- as well as people getting very comfortable with technology, and technology getting very good so that we can deliver products and services in a kiosk format or automated retail format.

I think people are getting much more used to getting products and services from an automated retail format. I see it expanding out.

One of the things we do at Coinstar, and have done, is we develop a relationship with our customers through the automated retail solution or the kisosk.

We do that through our email capture, and being able to have communication back and forth with them through having a good customer experience, to where people go to stores -- certain stores and certain kiosks -- because they've developed a relationship with Redbox or with Coinstar. We're going to look to continue to do that with some of our other products as well, as we bring it in the marketplace.

As we look out, we see it continuing to expand. We see it as being a way to sit in between that brick-and-mortar and the Web fulfillment. There's lots of opportunities for us in areas that we haven't even addressed yet.

Austin: You said you're neatly positioned between bricks-and-mortar and that Web experience. Those seem to be industries that have a lot of "once great" success stories here. There's a lot of once-great retailers out there; companies like Sears or J.C. Penney. There's also a lot of once-great tech companies out there: Apple famously down, Microsoft's not done a lot the past few years.

Given that you guys are at the intersection of that, what are you doing, as an executive and as a company, to continue the creative machine, to make sure that you guys stay relevant and avoid the pitfalls that are inherent in both of those industries?

Di Valerio: One of the things we always do is we start with the customer. We do a lot of work trying to understand what customer trends are, and what our customers want, and what new customers that would be coming to us would want.

We start there, and then start building backwards, about how do we develop a solution? If you look at our core businesses, the coin business, we're rolling out our PayPal solution, where you're able to load up your PayPal account with coins or cash, or withdraw from your PayPal account as well at our Coinstar machines.

What that does is open up Internet merchandising, or merchandisers, to maybe the under-banked and non-banked customers there, by being able to fill out your PayPal. Again, some adjacencies and extensions onto our business, that's physical, moving into the Web world.

If you think about our Redbox business, we have our tickets business that we're testing out, we have Reserve Online, so we're always stepping out past what we're doing from the physical presence as well.

We have a team that's really focused around new business ventures. We have Rubi -- which you guys have tasted -- the Rubi machine, our coffee business.

Austin: The reviews were good.

Di Valerio: That's right, good. Yeah, we have Crisp Market, which is prepared food in the breakfast and lunch daypart, and we have Star Studio, which is in the mall channel, which is a whole new take on photo booth, so green screens and music and fun, really geared toward the teenager that goes to the mall -- particularly the teen girls that go to the mall -- and making it a fun experience for them.

We continue to stretch out around those kinds of businesses in order to be able to bring new customers to the Coinstar brand, but also to bring new products to our customers and continue to extend out that relationship that we have with them.

Austin: It sounds like a lot of new products. I believe Rubi is, what, a partnership with Starbucks as well, right? Seattle's Best is a Starbucks label?

Di Valerio: Seattle's Best is a Starbucks label. We have an agreement with Seattle's Best in certain channels, to provide beans as well as to brand the machines. We certainly are a very good partner with them, but Rubi is 100% owned by Coinstar; we've generated business. It's a partnership that we have with them in bean supply, as well as obviously brand across key channels.

Austin: OK, so it looks like we have Rubi, some sort of food-based vending machines, and some photo-based vending machines. If you were to pick a "favorite child," so to speak, which one do you think has the most growth? Which one are you the most excited about, going out a few years?

Di Valerio: Certainly our Rubi machines. The other businesses are relatively early-stage businesses.

It's always hard to say, "OK, which one's going to hit?" Again, Crisp Market is performing well in the couple of stores that they're in today, the couple offices that they're in today. Star Studio is in around 60-70 mall locations and doing quite well, so we think that could be a nice business there.

We also have a business we call Sample It, which is beauty samples, today. Think about paying a dollar at a CVS or a Walgreen's [(WBA -0.93%)] for a couple samples of a cosmetic and a coupon. Not only do you, for a dollar, get to try out whether the product is going to work for you, but then you get a coupon to be able to purchase it.

The machines we have in market there are performing well, and the coupon redemption is quite high, which the brands love, as well as the retailers. In fact, Walgreen's just opened a brand-new banner store in downtown Boston and the sample machine was built into the store there, and again was a key focal point as they opened up the store.

Austin: Sample It! -- it seems like you've got some friendships with Walgreen's. I know you have a lot of kiosks with them. What other brands are people sampling? Is it Avon, is it... ?

Di Valerio: Yeah. Right now it's geared on beauty. We think it can extend to personal care and then on past that as well.

If you go into a Sample It! there will be a fragrance product from Halle Berry with the Halle Berry brand, Beyonce has branded products in there. It's across a number of the different traditional cosmetic brands. There's face products, there are fragrances, there are lotions, those kinds of things.

It's, again, starting there. Small samples you can test out, eye care products, see if it works for you and then be able to go back and buy the regular size.

Austin: Great. I want to talk about the specter in the room of Redbox; obviously your cash-cow business, you've had a lot of success with it, but a lot of the naysayers would say, "You guys are already at 50% market share, and the DVD rental industry is an eroding space."

I'm wondering, what is it about Redbox, and Coinstar in general, that is going to... what would you say to the naysayers who are looking at this industry and saying, "Well, it's eroding. How are you guys going to maintain relevance?"

Di Valerio: Certainly. One of the key things with the Redbox business is we continue to grow our market share and continue to increase overall rents by focusing on the customer and bringing a great new release product to the customer.

There's not a company that can deliver a new release product at the price point we do, and I think our customers are rewarding us for that. The first quarter of 2013, we have 40 million unique credit card transactions, which was up a million from the fourth quarter of 2012 and up over 6% from the year before, so we're growing our customer base.

We rented nearly 200 million discs in the first quarter, so we're continuing to grow out that business; that was an increase. What we're seeing, the NPD data shows that there's a slowing -- the decline in the physical rental market -- as the market has absorbed the demise of the brick-and-mortar stores, where lots of rentals were going, the national chains, and have converted to Redbox, for the most part.

You're seeing revenues come down in the rental market, but those revenues are coming down in large part because of the price point differential from, when you went to brick-and-mortar, you paid a higher price point than the $1.20 or $1.50 that you do at Redbox.

Austin: OK. I'm wondering if you could discuss the economics of your different kiosks, maybe useful life, the revenue generation that you see out of them, if you could, maybe across your big ones -- Coinstar, Redbox, Rubi.

Di Valerio: You bet. The Redbox kiosk is a kiosk that costs us about $15,000 to manufacture and put into the market. It pays back for itself in about 18 to 24 months. It begins positive cash flow in about eight to 12 months, so it's a very nice machine.

They start off, from a ramp perspective, $35,000 in year one in revenue, $50[,000] in year two and $55[,000] in year three, so it's a nice ramp-up business that returns on itself quite nicely, and continues to go out from that perspective.

The useful life of the machines, we have Redbox machines that have been in market since the start. We certainly bring machines in and refurbish them and do those types of things over time, but they're very stable, very long-lasting machines, and have been built quite well from that perspective.

Uptimes are extremely high on both the coin and the Redbox machines. In fact, on the Redbox machines about 85%-90% of any issues we have with the machines are resolved remotely, from our network operating center. There's very few break-fix services that go out on the machines.

The same is true with the Coinstar machine. Again, very high uptime on those. All the machines are connected wirelessly, so we communicate with the machines routinely during the day. We can fix issues on the machines routinely.

Again, it's a quite nice business. The coin machines are in the $11[,000]-$12,000-kiosk range.

Austin: That's cost to build?

Di Valerio: Cost to build. They pay back in a little bit longer time than the Redbox machine because it's got fewer transactions going through, but again we've had coin machines in the marketplace... 22 years that we've been in the business, we've had machines that are in the marketplace 15 years. They're very solid.

We're always having to replace monitors and upgrades, and do those kinds of things on a refurb basis, but they're very strong, long-lasting machines with high uptime.

Austin: Great. You guys, it seems, have retail relationships with everybody. You've got Safeway, Wal-Mart, CVS, Walgreen's I think we talked about earlier. I'm sure they're all great partners, but what's your favorite retail partner and why?

Is there one that just provides really great entry points for you, that you really enjoy working with, or do you see a lot of use from your machines at certain locations?

Di Valerio: It really depends on the business. For the coin business, what we've found is grocery and mass merch is the best way to go. It has enough traffic and has a high enough traffic pace to where people come into the stores and utilize machines and those kinds of things. The drug and convenience channel really don't work for the coin business.

We look at it from that perspective. A new, emerging market for us -- channel for us, I should say -- for the coin business is the financial institution business. We just put 350 kiosks in, in TD Bank Canada, and are processing points for TD Bank, and we're looking to expand.

We have a few machines in the U.S. today in the banking or financial institution channel and we're looking to expand that out as we go out.

It really depends on business from a channel perspective. When we look at Redbox, for example, we're in the grocery channel, we're in the mass merch channel, we're in convenience, and we're in drug, but we have the machines located at different places.

For convenience and drug, we're primarily outdoors. What that allows us to do is be open for 24 hours a day, it allows customers to see the machine, and it gets the right amount of traffic, both for us and as well for our retailers. And, again, it utilizes space that's very underutilized and turns it into very profitable space as well.

We really do focus based on the channel. If I look at some of our new businesses like Rubi, the grocery channel will be a very good channel for us. The mass merch channel will be a very good channel for us as well. I think we really do try to take a look at it based on the channels, as opposed to an individual retailer that's out there.

Austin: It's the right channel, the right placement, and the right machine is really what dictates it.

Di Valerio: Exactly.

Austin: Who would be the best retail partner that you don't already have? Who do you really want to become a partner with, that you haven't already tied the knot?

Di Valerio: We're very fortunate in the Redbox business, for example, that we have the top 10 national grocery chains under our banners. We have Wal-Mart, which is the largest mass merch center, as well as CVS and Walgreen's in the drug channel, and 7-Eleven and Circle K in convenience, so we have very, very strong channel space there.

With the coin business, we have nine of the 10 grocery chains under the coin banner, and Wal-Mart as well in the mass merch, so we have very strong relationships, as you've mentioned, across there. Certainly there are a couple on the coin side.

There's one grocery chain that we don't have, which we would love to bring up underneath the banner, which is Publix. Certainly, we always are looking and talking to Target as another large mass merch, to see if there are some opportunities with them for some of our businesses on a general basis.

Austin: OK. I wanted to talk a little bit about the progress of Redbox Instant and your partnership with Verizon [(VZ 2.85%)]. I'm wondering if you could maybe just elaborate on that, any progress you guys have going there, or what you're seeing as the early results?

Di Valerio: You bet. Yeah, we're very pleased with our partnership with Verizon, to bring Redbox Instant to the marketplace. We signed that deal in February of 2012, and about 15 months later were able to launch a product through kind of a beta, general availability. We're pleased with it so far.

One of the things we've been really doing is trying to understand from the customer, is there enough content between the around 5,000 titles that you have on the streaming side, as well as getting great new release content from the kiosk?

The surveys from our customers are saying yes, there's enough content, and they're finding great new-release content because you get four nights at the kiosk each month on the subscription, as well as the streaming, as we think about the business; that's both from customers who have stayed on and are paid subscribers, as well as ones who churned out of the business, so we're always trying to find the best mix there.

One of the great things about the Redbox Instant business is you basically have the full old brick-and-mortar store available to you.

If you think about it, when you used to go to a brick-and-mortar store you'd walk around the outside walls because that's where the new-release content was. We've taken that new-release content, and that's Redbox. Basically we've taken those outside walls and put them into 12 square feet. With Redbox Instant, we now have the center of the store available to our customers.

We think it's a great opportunity for our customers, it's a great value for our customers today at $8 for four standard-def rentals a month, plus unlimited streaming, or $9 for Blu-ray, for four nights at the kiosk.

We're really pleased; we think it's a great value for our customers, and as we roll into the third quarter, Redbox Instant will do a lot more work around promoting the service as we've brought on more CE device manufacturers so that people are going to get that 10-foot experience for being able to get it up on the TV in a much broader way.

Austin: Now, obviously there's a lot of incumbents in the streaming space. We can't talk about this without saying Netflix [(NFLX 4.17%)] and Amazon [(AMZN 1.30%)] Prime. Are they your biggest competitors here, or am I misreading it? Do you think about it differently?

Di Valerio: Yeah, I think our competitor is people's time, is what we look at. What are people going to choose to do for their entertainment value? Certainly those folks are in that space across there, plus a whole host of other people as well.

We think we are very well positioned because, for customers who love movies, you've got a service where you get new-release content. We're the only service that can bring new-release content, and the physical aspect of it, as well as the streaming in there.

What you're really doing is getting real new-release content when you want it, how you want it, and then be able to get your stream from around that.

Again, we're doing the business in a different way than some of the competitors on the streaming side. We are paying for content on a per-subscriber basis, which means each subscriber we bring on for Redbox Instant is gross margin positive.

It's different than... A lot of our competitors are buying content up front and having to build up the subscriber base in order to be able to cover off the costs, so they run negative a much longer time period than we will, from a profitability standpoint.

Because of the way that we're structured and running the business, we can be the No. 3 or No. 4 streaming business, and still be very, very successful, both for us and for Verizon.

Austin: It's because of that margin dynamic.

Di Valerio: The margin dynamic, and the fact that we're combining new-release content at the kiosk, on a physical basis, along with the stream, which is something that people are finding very compelling.

Austin: Now, the new-release issue has definitely been a user negative, leveled against Netflix and Verizon. What is it about you guys that allows you to bring new releases to users? I think a lot of people aren't really familiar with the dynamic of why some of the streaming people have to wait and why you're able to get the new-release content out there earlier, in front of users.

Di Valerio: There's a couple of ways to get new-release content from the studios. One is physical, which certainly we do here at the kiosk, and are really focused on that as a company. The other way is through what they call paid video on demand -- not the subscription video on demand -- so to pay $5-$6 to view a movie at home on your TV.

Really, we provide that same content at $1.20 for standard def and $1.50 for Blu-ray. People are continuing to buy Blu-ray players at very high rates. People love to get that physical disc and put it in, because there isn't a better way, from a Blu-ray perspective, to get really high-definition-quality picture and sound. The way you get it is through the disc. You can't get that through a stream.

We feel very good about that. We obviously are focused on it, and we think that combination, as you look at Redbox Instant, combined with Redbox on the physical side, is a winning combination.

Austin: Good combo there for users.

What's next in the pipeline for Coinstar? You guys obviously are rolling out a lot of new devices, looking at new automated kiosks. What else is there for users, that they should be looking forward to over the next few years?

Di Valerio: We're going to continue to look and bring great automated retail solutions. Certainly, with our coin line of business we are rolling out the PayPal, so that's a great opportunity for people to lever their PayPal accounts and do some things they want to do there.

We also have a business in the coin business called Gift Card Exchange, where you can exchange your gift cards that you've been getting for years, at stores that you might not go to, or stores that you have a little bit of money left on those cards, and get those turned in for cash.

We think that's going to be a very interesting business for us. We're starting to roll that business out. There's around 50 kiosks in the market today and we'll expand that out over the next year to capture that, and also be looking to do that with both your physical gift card, but also your digital gift cards, to be able to be the place where you're turning in your gift cards and then we're remonetizing those out.

As I look at Redbox, for example, we're obviously beginning to roll out Redbox Instant in a broader fashion, along with Verizon. We're testing tickets out, and we're putting in some very good CRM and loyalty programs that will roll out in the third and fourth quarters that will continue to extend out that Redbox brand and value: simplicity, convenience, and entertainment.

We are the No. 1 place for people to watch new-release content. We want to be the No. 1 place that people come to for overall entertainment.

If I look at the business broader, we think there are some great opportunities to bring new products into the marketplace, but also to extend them out, both from a physical perspective as well as from an online perspective, and keep marrying those two things up as we go forward.

Austin: Great. You guys have dramatically reduced shares outstanding in just a few quarters. I think it was about 3 million shares. I'm wondering, now that you're CEO, if you could discuss the logic and strategy behind that share repurchase program and whether or not you guys are interested in continuing it?

Di Valerio: You bet. We do capital allocation on a holistic basis. You first take a look and say, "OK, I need to invest in my core businesses to continue to grow them, both from new innovations into the core businesses, as well as the existing. I need to invest in new businesses" -- like we've been talking about -- "to bring new concepts into the marketplace, and then also in infrastructure in the corporation."

You calculate out what those returns are, and also returning money to the shareholders through share buyback. We'll continue to do that. We balance those out to make sure that we're doing it in a smart way, but a way that really does drive the highest return.

Four years ago, our return on invested capital, for example, was in the low single digits. Last year we finished out at 18.3%.

Austin: Congratulations.

Di Valerio: It's a nice focus for us to continue to do that, and as we try to grow out this business -- and we've talked about doubling the size of the company over the next five years -- we're going to do that while getting our return on invested capital up to 20%, which isn't necessarily the easiest thing to do, but that's how we stay in this very structured and balanced approach to getting returns for our shareholders.

Austin: Got to aim high.

Di Valerio: That's right.

Austin: What do you think is the single biggest thing that retail investors may be missing, or should know, about Coinstar today?

Di Valerio: It's a business that really focuses on its customer, and it's a business that is very operationally sound, and a business that continues to be inventive, innovative, and to bring new products to the market that customers want, and do it in a way that's efficient and effective, that's driving top-line and bottom-line growth.

If you look at our business, we've grown double-digits over the last four or five years, both top line and bottom line, and we've driven great free cash flow: well over $250 million of free cash flow last year, we'll generate between $185 [million] and $205 million of free cash flow this year.

It's a business that's very strong, very growth-oriented, but we're growing profitability at the same time we're growing revenue and free cash flows, which is, again, a business that is very good to run. It's a business that should be very good to invest in, and one that's probably a little bit misunderstood, given the fact that we have a lot of great businesses and we're in a business that we think is going to continue to grow, and grow quite rapidly.