Mobile Edge Computing (MEC) has envisioned to be a promising technology to provide more efficient services for computation-intensive but delay-sensitive onboard mobile services. In this paper, the Non-Orthogonal Multiple Access (NOMA) technology is applied in a vehicular edge computing network, in which vehicular users (VUs) can offload partial computation tasks to MEC servers over wireless channels for remote execution. In this network, an optimization problem for the long-term energy consumption of the system is presented and aims to minimize it by jointly optimizing the Successive Interference Cancellation (SIC) ordering of NOMA, the VUs’ transmit power for computation offloading, and computation resource allocation of the MEC server. To deal with the intractable long-term optimization problem, we first transform it into an equivalent instantaneous form based on the Lyapunov optimization theory. Since the transformed problem is still highly non-convex, we further decompose it into the interactive resource allocation and SIC ordering sub-problems. For the resource allocation sub-problem, we exploit its convexity through the transformation and reparameterization, and derive the optimal solution in accordance with the Karush-Kuhn-Tucker (KKT) conditions and the gradient descent algorithm. After that, we propose a low-complexity algorithm by leveraging the Tabu search to obtain the sub-optimal SIC ordering. Simulation results validate the effectiveness of the proposed algorithm and the superiority of NOMA compared to Frequency Division Multiple Access (FDMA).