In this paper, we focus on necessary and sufficient efficiency conditions for optimization problems with multiple objectives and a feasible set defined by interval-valued functions. A new concept of Fritz-John and Karush–Kuhn–Tucker-type points is introduced for this mathematical programming problem based on the gH-derivative concept. The innovation and importance of these concepts are presented from a practical and computational point of view. The problem is approached directly, without transforming it into a real-valued programming problem, thereby attaining theoretical results that are more powerful and computationally more efficient under weaker hypotheses. We also provide necessary conditions for efficiency, which have been inexistent in the relevant literature to date. The identification of necessary conditions is important for the development of future computational optimization techniques in an interval-valued environment. We introduce new generalized convexity notions for gH-differentiable interval-valued problems which are a generalization of previous concepts and we prove a sufficient efficiency condition based on these concepts. Finally, the efficiency conditions for deterministic programming problems are shown to be particular instances of the results proved in this paper. The theoretical developments are illustrated and justified through several numerical examples.