Researchers often use survey methods to elicit patient perspectives on their healthcare. Survey results are often subject to response bias and missing data. As part of an observational study of Veterans’ healthcare preferences, we conducted a national survey of Veterans receiving care in the Veterans Affairs healthcare system. We describe two recruitment strategies offering concurrent online, paper, and phone survey options to different sets of participants and examine response and missingness patterns between recruitment methods and modalities. In Strategy 1 we sent recruitment letters presenting options to complete our survey online or on paper. If patients indicated that they wanted to complete a paper survey, we mailed them a paper survey. In Strategy 2 we sent recruitment letters with paper surveys and included the option to complete the survey online. We compared response rates, characteristics, and missingness for the strategies and survey modalities. We sent 4399 initial letters using Strategy 1 and 8148 initial letters using Strategy 2 with response rates 7.7% and 13.2%, respectively; 70.6% of respondents completed paper surveys. Across both strategies, paper survey respondents were older and had lower educational attainment. There were significantly more paper surveys missing greater than 2% of items than online surveys (OR 6.3, 95% CI [4.8, 8.1]). Our findings suggest tradeoffs associated with survey modality and recruitment strategies. Mixed-modality recruitment may increase response rates and decrease missing data and response bias. Researchers should consider their target population when choosing survey modalities given differing characteristics between paper and survey respondents.