In order to be successful in the market in the long term, enterprises must not only continuously optimize their operations but also constantly innovate. It is necessary to develop radically new digital services which disrupt their existing business model. For small and medium-sized enterprises (SMEs), it is a major challenge to put the generated solutions into practice. They have to cope with digitalization while having limited resources. The presented paper starts by examining the challenges for SMEs in the context of digitalization. Thus, an analysis of the approaches used in practice for implementing digital services in 36 SMEs is carried out. Essential differences between start-ups and established SMEs are identified. On this basis, a capability-based, agile methodology is presented which supports enterprises in advancing newly developed, digital services from prototype status to the customer’s environment. Finally, the methodology is put into practical application within an innovation project in an SME.