This paper compares bicycling in Washington, DC and Frankfurt am Main, Germany, two car-oriented cities that had adapted their urban transport system to car travel during the 20th century. Our comparative case study shows that both cities have been successful in increasing the percentage of trips made by bicycle between the late 1990s and 2018: Washington, DC from 1% to 5% and Frankfurt from 6% to 20% of trips. Both cities had detailed bike plans and specific mode share goals for bicycling. However, those plans were only used as guideposts for a step-by-step approach to bicycle promotion that focused on integrating bicycling into everyday decision making in transport, traffic engineering, and urban development. This step-by-step approach successfully garnered political, public, and administrative support over time. The downside of this incrementalist approach is that bike route networks in both cities still have many gaps because bikeway infrastructure was built when individual opportunities arose and not as part of an integrated network. Bicycle promotion in both cities used a combination of bikeway infrastructure and soft policy, including marketing measures. In both cities, the quality of newly installed bikeway infrastructure increased over time from simple bike lanes to protected bike lanes separating cyclists from traffic. In contrast to Washington, DC, Frankfurt has a longer history of car-restrictive policies and overall has been more strict in limiting car use.