We present an adaptive remeshing algorithm for meshes of unstructured triangles in two dimensions and unstructured tetrahedra in three dimensions. The algorithm automatically adjusts the size of the elements with time and position in the computational domain in order to resolve the relevant scales in multiscale physical systems to a user-prescribed accuracy while minimizing computational cost. The optimal mesh that provides the desired resolution is achieved by minimizing a spring-like mesh energy function that depends on the local physical scales using local mesh restructuring operations that include edge-swapping, element insertion/removal, and dynamic mesh-node displacement (equilibration). The algorithm is a generalization to volume domains of the adaptive surface remeshing algorithm developed by Cristini et al. [V. Cristini, J. Blawzdziewicz, M. Loewenberg, An adaptive mesh algorithm for evolving surfaces: simulations of drop breakup and coalescence. J. Comp. Phys., 168 (2001) 445] in the context of deforming interfaces in two and three dimensions. The remeshing algorithm is versatile and can be applied to a number of physical and biological problems, where the local length scales are dictated by the specific problem. In Part II [X. Zheng, J. Lowengrub, A. Anderson, V. Cristini, Adaptive unstructured volume remeshing - II: application to two- and three-dimensional level-set simulations of multiphase flow, J. Comp. Phys., in press], we illustrate the performance of an implementation of the algorithm in initeelement/ level-set simulations of deformable droplet and fluid-fluid interface interactions, breakup and coalescence in multiphase flows.