The Appointment Scheduling Problem (ASP) involves scheduling a finite number of customers with uncertain service times, served consecutively by a single server with the goal of minimizing the weighted costs of waiting time, idle time, and overtime, which can be written as a sum-of-max linear functions. We introduce a novel robust optimization approach that considers service times within a specified uncertainty set and minimizes the worst-case costs, necessitating the maximization of a convex function. By integrating advanced methods from robust convex optimization, such as the reformulation-perspectification technique and a cutting-set approach, we are the first to establish a general and exact solution procedure for determining optimal schedules, thereby advancing limited prior work that we show rely on restrictive, inefficient or incorrect formulations. Our robust framework for the ASP is designed to handle large instances and accommodates general convex uncertainty sets. In particular, we demonstrate its implementation for polyhedral, ellipsoidal, and conic-representable uncertainty sets. Based on extensive numerical experiments involving up to 100 customers, we reveal intricate interactions between the uncertainty of service times, the cost function, and the structural characteristics of optimal schedules.