Video analytics constitute a core component of many wireless services that require processing of voluminous data streams emanating from handheld devices. Multi-Access Edge Computing (MEC) is a promising solution for supporting such resource-hungry services, but there is a plethora of configuration parameters affecting their performance in an unknown and possibly time-varying fashion. To overcome this obstacle, we propose an Automated Machine Learning (AutoML) framework for jointly configuring the service and wireless network parameters, towards maximizing the analytics’ accuracy subject to minimum frame rate constraints. Our experiments with a bespoke prototype reveal the volatile and system/data-dependent performance of the service, and motivate the development of a Bayesian online learning algorithm which optimizes on-the-fly the service performance. We prove that our solution is guaranteed to find a near-optimal configuration using safe exploration, i.e., without ever violating the set frame rate thresholds. We use our testbed to further evaluate this AutoML framework in a variety of scenarios, using real datasets.