Tobacco-free (TF) college campus policies have potential to be a high-impact tobacco control strategy. The purposes of the study presented here were to (a) determine the demographic and personal characteristics associated with students’ beliefs about and perceived effectiveness of a TF campus policy and (b) assess whether tobacco use status and exposure to secondhand smoke (SHS) predicted beliefs and perceived effectiveness. Five thousand randomly selected students from a large southeastern university were invited by e-mail to participate in an online survey in April 2013, three and a half years after policy implementation. Students held positive beliefs about the policy (average rating 84% of the maximum possible score). Sixty-one percent believed that the policy was successful at reducing SHS exposure; and 40% thought the policy encouraged quitting. Males were less likely than females to believe the policy was effective in reducing SHS exposure and encouraging quitting. Lower undergraduates were more likely to perceive the policy as less effective in reducing SHS exposure; international students were more likely than domestic students to perceive the policy as more effective at encouraging quitting. Students most exposed to SHS were less likely to perceive the policy was effective. Compared with nonusers, those who smoked cigarettes were less likely to perceive the policy as effective in encouraging quitting. Tailored messaging regarding policy benefits are necessary. Perceived effectiveness of TF policies may be related to compliance with the policy and should be further investigated. Objective measures of effectiveness and tobacco use behaviors are needed to fully measure the success of TF campus policies.