There is a wide consensus on the benefits of software traceability. However, traceability techniques are still not commonly used in industry - typically only in larger companies and if mandated by standards such as the CMMI or ISO 15504. Success stories in small companies are quite rare. However, small companies represent a significant share of the IT industry and a better understanding of their needs is essential for the research community. This paper presents APIS, a traceability environment we developed and introduced in a very small software company. We discuss the traceability approach and report on key lessons learned. We have found in the project that comparably simple automation techniques are surprisingly effective. We believe that the lessons learned in this project are relevant for researchers and practitioners facing similar challenges.