BACKGROUND: Challenges in implementing electronic health records (EHRs) have received some attention, but less is known about the process of transitioning from legacy EHRs to newer systems. OBJECTIVE: To determine how ambulatory leaders differentiate implementation approaches between practices that are currently paper-based and those with a legacy EHR system (EHR-based). DESIGN: Qualitative study. PARTICIPANTS: Eleven practice managers and 12 medical directors all part of an academic ambulatory care network of a large teaching hospital in New York City in January to May of 2006. APPROACH: Qualitative approach comparing and contrasting perceived benefits and challenges in implementing an ambulatory EHR between practice leaders from paper- and EHR-based practices. Content analysis was performed using grounded theory and ATLAS.ti 5.0. RESULTS: We found that paper-based leaders prioritized the following: sufficient workstations and printers, a physician information technology (IT) champion at the practice, workflow education to ensure a successful transition to a paperless medical practice, and a high existing comfort level of practitioners and support staff with IT. In contrast, EHR-based leaders prioritized: improved technical training and ongoing technical support, sufficient protection of patient privacy, and open recognition of physician resistance, especially for those who were loyal to a legacy EHR. Unlike paper-based practices, EHR-based leadership believed that comfort level with IT and adjustments to workflow changes would not be difficult challenges to overcome. CONCLUSIONS: Leadership at paper- and EHR-based practices in 1 academic network has different priorities for implementing a new EHR. Ambulatory practices upgrading their legacy EHR have unique challenges.