Efficient structure search is a major challenge in computational materials science. We present a modification of the basin hopping global geometry optimization approach that uses a curvilinear coordinate system to describe global trial moves. This approach has recently been shown to be efficient in structure determination of clusters [C. Panosetti et al., Nano Lett. 15, 8044-8048 (2015)] and is here extended for its application to covalent, complex molecules and large adsorbates on surfaces. The employed automatically constructed delocalized internal coordinates are similar to molecular vibrations, which enhances the generation of chemically meaningful trial structures. By introducing flexible constraints and local translation and rotation of independent geometrical subunits, we enable the use of this method for molecules adsorbed on surfaces and interfaces. For two test systems, trans-β-ionylideneacetic acid adsorbed on a Au(111) surface and methane adsorbed on a Ag(111) surface, we obtain superior performance of the method compared to standard optimization moves based on Cartesian coordinates.