Non-Markovian dynamics pervades human activity and social networks and it induces memory effects and burstiness in a wide range of processes including inter-event time distributions, duration of interactions in temporal networks and human mobility. Here we propose a non-Markovian Majority-Vote model (NMMV) that introduces non-Markovian effects in the standard (Markovian) Majority-Vote model (SMV). The SMV model is one of the simplest two-state stochastic models for studying opinion dynamics, and displays a continuous order-disorder phase transition at a critical noise. In the NMMV model we assume that the probability that an agent changes state is not only dependent on the majority state of his neighbors but it also depends on his {em age}, i.e. how long the agent has been in his current state. The NMMV model has two regimes: the aging regime implies that the probability that an agent changes state is decreasing with his age, while in the anti-aging regime the probability that an agent changes state is increasing with his age. Interestingly, we find that the critical noise at which we observe the order-disorder phase transition is a non-monotonic function of the rate $beta$ of the aging (anti-aging) process. In particular the critical noise in the aging regime displays a maximum as a function of $beta$ while in the anti-aging regime displays a minimum. This implies that the aging/anti-aging dynamics can retard/anticipate the transition and that there is an optimal rate $beta$ for maximally perturbing the value of the critical noise. The analytical results obtained in the framework of the heterogeneous mean-field approach are validated by extensive numerical simulations on a large variety of network topologies.