This paper aims to determine the potential of the bicycle as a sustainable mode of transport in a medium-sized Spanish city (Santander, in northern Spain) with strong inclines and relatively inclement weather. For this purpose, a general methodology has been designed that could serve as an example for other areas. First, potential bicycle users in the city are characterized and identified through a household survey, which included a complete travel diary. Then they were asked to participate in a stated preference survey designed to find out the relative importance of certain key variables, previously identified, associated with making bicycle journeys. These data were used to estimate mixed logit models allowing to correctly treat the pseudopanel nature of the data. The results indicate that the most important variables among potential users are the cost and the climate, followed by the availability of infrastructure such as cycle paths and an extensive network of both public and private bicycle docking stations. Finally, the willingness to change from traditional modes of transport, such as car and bus, to bicycle has been examined according to various policies designed to encourage more sustainable mobility (such as bicycle and bus lanes and a city center congestion charge for private cars). The main finding of this research has been the identification of the conditions under which the bicycle could increase its market share from its current 0.30% up to 5.52% in a city with the characteristics of Santander (i.e., not in principle conducive to expect high bicycle use).