Habit formation may be important to maintaining repetitive healthy behaviors like exercise. Existing habit questionnaires only measure part of the definition of habit (automaticity; frequency). A novel habit questionnaire was evaluated that measured contextual cueing. We designed a two-stage observational cohort study of regular exercisers. For stage 1, we conducted an in-person interview on a university campus. For stage 2, we conducted an internet-based survey. Participants were 156 adults exercising at least once per week. A novel measure, The Exercise Habit Survey (EHS) assessed contextual cueing through 13 questions on constancy of place, time, people, and exercise behaviors. A subset of the Self-Report Habit Index (SRHI), measuring automaticity, was also collected along with measures of intention and self-efficacy, and the International Physical Activity Questionnaire (IPAQ), leisure-time section. The EHS was evaluated using factor analysis and test-retest reliability. Its correlation to other exercise predictors and exercise behavior was evaluated using Pearson's r and hierarchical regression. Results suggested that the EHS comprised four subscales (People, Place, Time, Exercise Constancy). Only Exercise Constancy correlated significantly with SRHI. Only the People subscale predicted IPAQ exercise metabolic equivalents. The SRHI was a strong predictor. Contextual cueing is an important aspect of habit but measurement methodologies warrant refinement and comparison by different methods.