Expressions for analytical molecular gradients of core-excited states have been derived and implemented for the hierarchy of algebraic diagrammatic construction (ADC) methods up to extended second-order within the core-valence separation (CVS) approximation. We illustrate the use of CVS-ADC gradients by determining relaxed core-excited state potential energy surfaces and optimized geometries for water, formic acid, and benzene. For water, our results show that in the dissociative lowest core-excited state, a linear configuration is preferred. For formic acid, we find that the O K-edge lowest core-excited state is non-planar, a fact that is not captured by the equivalent core approximation where the core-excited atom with its hole is replaced by the "Z + 1" neighboring atom in the periodic table. For benzene, the core-excited state gradients are presented along the Jahn-Teller distorted geometry of the 1s -> pi* excited state. Our development may pave a new path to studying the dynamics of molecules in their core-excited states.