We study Euclidean Wilson loops at strong coupling using the AdS/CFT correspondence, where the problem is mapped to finding the area of minimal surfaces in Hyperbolic space. We use a formalism introduced recently by Kruczenski to perturbatively compute the area corresponding to boundary contours which are deformations of the circle. Our perturbative expansion is carried to high orders compared with the wavy approximation and yields new analytic results. The regularized area is invariant under a one parameter family of continuous deformations of the boundary contour which are not related to the global symmetry of the problem. We show that this symmetry of the Wilson loops breaks at weak coupling at an a priori unexpected order in the perturbative expansion. We also study the corresponding Lax operator and algebraic curve for these solutions.