In this article, we aim to minimize the Age of Information (AoI) for a random access Internet of Things (IoT) network, where AoI is a metric to measure the freshness of information delivery. Since nonorthogonal multiple access (NOMA) can improve network throughput and connectivity, we exploit an AoI-oriented NOMA-based random access scheme, wherein devices simultaneously access wireless channel over multiple power levels with different access probabilities when their AoIs is not smaller than a threshold. We first study the comprehensive steady-state analysis of an AoI-independent NOMA-based random access scheme, which is a special case when the threshold is one. The AoI evolution is formulated as a Markov chain based on the analyzed transmission success probability, and the probabilities of AoI states and the achieved AoI under generate-at-will are derived. Then, an AoI minimization algorithm is proposed to optimize the power access probabilities. Concerning stochastic-arrival, the steady-state probabilities of devices’ active state, successful transmission, and the number of active devices are derived to analyze the expected AoI. Finally, the steady-state probabilities of AoI states and the achieved AoI of AoI-dependent NOMA-based scheme are obtained. Simulation results validate our analysis and demonstrate the significant performance improvement in terms of AoI. In specific, the proposed scheme can achieve AoI reduction by 65%, compared with random access without NOMA.