Background: Although secure messaging (SM) between patients and clinical team members is a recommended component of continuous care, uptake by patients remains relatively low. We designed a multicomponent Supported Adoption Program (SAP) to increase SM adoption among patients using the Veterans Health Administration (VHA) for primary care. Objective: Our goals were to (1) conduct a multisite, randomized, encouragement design trial to test the effectiveness of an SAP designed to increase patient engagement with SM through VHA's online patient portal (My HealtheVet [MHV]) and (2) evaluate the impact of the SAP and patient-level SM adoption on perceived provider autonomy support and communication. Patient-reported barriers to SM adoption were also assessed. Methods: We randomized 1195 patients at 3 VHA facilities who had MHV portal accounts but had never used SM. Half were randomized to receive the SAP, and half served as controls receiving usual care. The SAP consisted of encouragement to adopt SM via mailed educational materials, proactive SM sent to patients, and telephone-based motivational interviews. We examined differences in SM adoption rates between SAP recipients and controls at 9 months and 21 months. Follow-up telephone surveys were conducted to assess perceived provider autonomy support and self-report of telephone communication with clinical teams. Results: Patients randomized to the SAP had significantly higher rates of SM adoption than the control group (101/595, 17.0% vs 40/600, 6.7%; P<.001). Most adopters in the SAP sent their first message without a motivational interview (71/101, 70.3%). The 10-percentage point difference in adoption persisted a full year after the encouragement ended (23.7%, 142/600 in the SAP group vs 13.5%, 80/595 in the control group, P<.001). We obtained follow-up survey data from 49.54% (592/1195) of the participants. SAP participants reported higher perceived provider autonomy support (5.7 vs 5.4, P=.007) and less telephone use to communicate with their provider (68.8% vs 76.0%, P=.05), compared to patients in the control group. Patient-reported barriers to SM adoption included self-efficacy (eg, not comfortable using a computer, 24%), no perceived need for SM (22%), and difficulties with portal password or login (17%). Conclusions: The multicomponent SAP was successful in increasing use of SM 10 percentage points above standard care; new SM adopters reported improved perceptions of provider autonomy support and less use of the telephone to communicate with their providers. Still, despite the encouragement and technical assistance provided through the SAP, adoption rates were lower than anticipated, reaching only 24% at 21 months (10% above controls). Common barriers to adoption such as limited perceived need for SM may be more challenging to address and require different interventions than barriers related to patient self-efficacy or technical difficulties.