A new mobility ethos is needed for cities looking to overcome the problems that have been accumulated for decades by a transport paradigm that prioritises automobiles over people. Bike-sharing, a measure promoting voluntary travel behaviour change, could be part of a refined toolbox that will help in forging this new ethos. Despite a rapid emergence during the last handful of years, as evidenced by 1956 operational local schemes and approximately 15,254,400 self-service public use bicycles across the world, bike-sharing has been attracting negative attention lately. Tens of schemes have closed down, deemed as financial or operational failures, stigmatising bike-sharing's brand and putting the future of the concept itself in jeopardy. However, discounting bike-sharing as flawed may not be fair or accurate. This paper identifies a formula of success for bike-sharing operations based on a state-of-the-art case study analysis, which is supported by primary data evidence from two survey-based studies in Sweden and Greece. This paper suggests that residents in cities hosting or looking to host bike-sharing schemes are usually very supportive of them but not always likely to use them. More importantly, this paper delivers some key policy and business lessons that form a survival guide for effectively introducing and running public bicycle schemes. These lessons include, among others, the need for: tailoring the system design and expansion strategy according to the host city needs, city-operator and commercial partner synergies, more bike-friendly infrastructure and legislation, pro-active cultural engagement, anti-abuse measures, enhanced fleet management and realistic profit expectations.