The Warrior to Soul Mate (W2SM) program is a grassroots initiative on the part of Veterans Affairs chaplain services to provide relationship enhancement skills to veterans and significant others based on the Practical Application of Intimate Relationship Skills model. To examine the implementation and sustainability of the W2SM program, two online surveys were sent to each participating facility's W2SM leader. The first examined how individual W2SM events were conducted (100% response rate, 67 surveys) and the second assessed facility-level issues impacting program sustainability (100% response rate, 23 surveys). Four sites were selected for qualitative interviews based on levels of sustainability. In 2013, W2SM served 1,664 people including 847 veterans, incurring reasonable program costs when compared to other intensive Veterans Affairs services. However, there have been important systematic (e.g., contracting processes) and resource (e.g., time, concern over funding) challenges that are reflected in the wide range of predicted program sustainability.