Stasher’s journey: a Q&A with Anthony Collias

Stasher is a luggage storage platform, connecting travellers with over 8,500 vetted locations across 75+ countries. What started as Oxford roommates charging friends to store bags near King's Cross has evolved into a profitable, multi-million pound business that's transforming urban travel infrastructure.

If you could go back in time, what one piece of advice would you give your pre-startup self?

Don't overthink the "big vision" at the start. Our original pitch was this grand "Airbnb for storage" concept – any items, anyone's home, everywhere. It sounded impressive in pitch competitions, but it was too broad to execute properly.

What actually worked was narrowing down ruthlessly. We focused on luggage storage in specific cities with verified business partners. That specificity let us nail the operations, build trust through vetting, and actually solve a real problem people had every single day.

The lesson, for me, is: start narrow and get excellent at one thing, then expand from that position of strength. We're now in 1,000+ cities globally, but we got there by perfecting London first. Grand visions are great for pitch decks, but tight execution in a specific niche is what builds actually successful businesses.

What is one failure you experienced during the journey, and what did you learn from it?

We raised our Series A literally weeks before COVID hit. At first, that felt like catastrophic timing – 15% of our partner network went bankrupt almost overnight. Travel essentially stopped. We saw our revenue drop while still having a team to pay and investors who'd just placed their trust in us.

But actually, what happened is that it forced us to become a lot more efficient. Pre-COVID, we'd visit potential partners in person, have long sales cycles, do everything quite manually. When that became impossible, we had to automate everything - outreach, onboarding, support systems. We built tools out of necessity that made us far more scalable.

The bigger learning was about market timing in two-sided marketplaces. The pandemic actually accelerated small business digitisation. Corner shops in Sydney that would never have replied to emails before were suddenly checking them daily, doing online orders, looking for additional revenue streams. When we came back, our old manual approach wouldn't have scaled - but our new systems could onboard hundreds of locations monthly without anyone leaving their desk.

Sometimes the worst timing forces you to build the muscles you'll need for the next phase.

Did you make any assumptions about your market that turned out to be incorrect? How did you pivot?

One that I can think of is that we assumed luggage storage would be like hotel bookings – people planning ahead, booking days or weeks in advance. That's how we designed our early marketing and pricing.

It turns out that 90% of our bookings are same-day. People realise they need storage that morning when they're checking out of their Airbnb or hotel at 10am with a flight at 9pm. It's not planned infrastructure like accommodation – it's on-demand logistics, more like an Uber than a hotel.

That insight influenced our product strategy. We optimised for instant bookings, real-time availability, locations near transport hubs rather than tourist attractions. We also realised this behaviour makes luggage storage incredibly defensible – whoever has the most locations in the right spots owns the market, because users don't have time to shop around.

The other assumption that proved wrong: we thought people would worry about trust and security in the actual shop so we built a lot of guardrails and FAQ content on this. And actually, people do care about this, but it doesn't stop them booking.

We have 4.8 stars on Trustpilot from 3,000+ reviews. What we learned is that if you nail the basics – instant confirmation, clear location, insurance guarantee - trust comes from execution, not from messaging about it.

Describe a moment when you thought your startup might not succeed. How did you overcome this?

There was a period about a year ago where four major issues hit us simultaneously. We were having trouble getting approved on Google Maps – a critical channel for us – while our competitors were already live. An SEO algorithm update affected our rankings. We had Google Ads tracking issues compounded by implementing cookie consent, which disrupted our attribution for weeks. And one of our major Online Travel Agency distribution channels paused us because our cancellation rate was 1% when they wanted 0.5%.

These four problems converging created a scary few weeks where our growth stalled to barely being up year-on-year. In context, that doesn't sound catastrophic – we didn't even dip below the previous year – but when you don't know where the bottom is, it feels like free fall.

How did we overcome it? There was no magic solution. We identified the four specific problem areas, divided them up, and systematically worked through each one. The improvements gradually compounded until they counteracted the downward slide and turned into an upward trajectory.

The lesson for me was twofold. First, being capital-efficient meant we weren't over-leveraged, so we had breathing room to turn things around. Second, especially in consumer businesses, you need to resist the temptation to obsess over daily fluctuations. Most day-to-day movement is noise. Once you reach a certain scale, you need to think in terms of weeks and months, not days. That mental discipline is crucial when things get rough – and that sometimes means that when shit hits the fan, you need to take a deep breath and say "ok, let’s take the actions that make sense and see where we're at in a couple weeks" – and avoid the temptation to check for changes every few hours.

How did you approach creating an authentic company culture, and what unique aspects of your culture do you think have contributed to your success?

I'd highlight three cultural principles that have been critical: high autonomy, high trust, and not undervaluing retention.

On autonomy and trust: every time we hire someone, it should be because there's too much on our plate and that person should take work off our plate. If you introduce systems where you suddenly need to micromanage people heavily, the balance doesn't work. So we hire autonomous people we trust, often pay a bit more for that, don't push them too hard on hours, and reward them well with equity. The exchange is that's how you find people who actually take work off your plate rather than pile on management overhead.

On retention: it's easy to undervalue retention because it's an invisible cost. The loss in efficiency when someone leaves, the time spent hiring and onboarding their replacement, the ramp-up period, the higher salary you'll probably pay the new person - these costs aren't line items in your bank account, but they're massive. Our average tenure is four or five years, and you probably get the best out of people after year two. When you raise less capital and need to be more careful with spending, you naturally attract people who are bought in.

Honestly, these cultural choices weren't calculated to maximise mid-term profit. We tried to make a company we could sustainably work at ourselves, and these were our requirements.

What piece of conventional wisdom about startups do you disagree with?

"Grow at all costs" and "winner-takes-all requires being biggest fastest." We're profitable and growing really strongly, while our main competitors have raised tens of millions more than us.

The conventional wisdom in marketplace businesses is you need massive VC rounds to subsidise growth, underprice competitors and grab market share before worrying about unit economics. Maybe that works in some markets, but we've found that profitability with strong growth beats hyper-growth with an unclear path to profits.

Also, in luggage storage in particular, the winning factors are location quality, customer trust (reviews), and operational reliability. Throwing money at user acquisition doesn't solve those. A poorly-located StashPoint with mediocre service doesn't become good just because you spent more on ads.

We've prioritised sustainable growth – hitting profitability in 2024, maintaining >100% YoY revenue growth, expanding to 1,000+ cities. We'll raise our Series A when we find the right partner who gets that approach. But we won't sacrifice unit economics for vanity metrics. The best businesses in travel - Booking.com, Airbnb after the early years – eventually all had to prove they could make money. We'd rather build that in from the start.

I'd also challenge the assumption that winner-takes-all always applies to VC-fundable businesses. It's sometimes the case, but not always. Not all network-effect businesses are homogenous and replaceable.

Everyone points to Uber as the example of winner-takes-all, but globally there's a handful of multi-billion pound transport companies. A large part of why Uber is "winning" overall is because they built food delivery alongside rides - these became each other's biggest acquisition channels. It's more about their platform strategy than pure network effects.

Compare Uber to WhatsApp - communication networks tend to capture close to 100% of markets when they're dominant. That's clearly not the case with ride-hailing. And luggage storage is even more fragmented than ride-hailing because it's extremely location-specific. People tend to redo their search every time based on their exact location, rather than defaulting to one app.

What were the best support systems you’ve relied on throughout your startup journey?

Two things stand out: my co-founder relationship with Jacob, and being able to be honest with our team.

On the co-founder front, having someone whose temperament and approach matches your own is invaluable when things get tough. You're going through the same challenges, the same stress, and having that shared understanding makes it manageable.

The team honesty piece is also crucial. If things are going badly and you can't honestly discuss that with the people you're working with, that's an incredibly stressful situation. Building a culture where we can be transparent about challenges – whether it's the difficult month we're having or the strategic uncertainty we're navigating – makes everything significantly easier. That transparency and trust also helps us solve problems faster because everyone has the full context.

On a personal level, I'd add that having an understanding partner matters enormously. You want someone whose lifestyle and temperament matches what's going on with your work. For some people that means having a partner with an equally demanding job. For others it means the opposite – it would be too much strain for both to have very demanding roles. There's no universal answer, but the alignment matters.

For more startup news, check out the other articles on the website, and subscribe to the magazine for free. Listen to The Cereal Entrepreneur podcast for more interviews with entrepreneurs and big-hitters in the startup ecosystem.