Sartre did use the expression "existence precedes essence" as a motto, but his implied critical target was not Aristotle's general essence theory. It was, rather, the specific idea of human nature. Sartre's expression was meant to express the existentialist stand, that a human being's way in life is not chosen for him in advance, by his own nature or origin. That one has to choose one's way, and that one is free to do so.
What do we mean by saying that existence precedes essence? We mean that man first of all exists, encounters himself, surges up in the world – and defines himself afterwards. If man as the existentialist sees him is not definable, it is because to begin with he is nothing. He will not be anything until later, and then he will be what he makes of himself. Thus, there is no human nature, because there is no God to have a conception of it. Man simply is. (Existentialism is Humanism)
The order of Descartes's Cogito
(I think, I exist) was epistemological, and Sartre did not challenge it as such. What Sartre did challenge, was Descartes's Cogito-related metaphysical conclusion that the I was a thinking substance.
The I that appears on the horizon of the 'I think' is not given as a producer of conscious spontaneity. Consciousness is produced over against it and moves towards it, comes to meet it. This is all that can be said. (The Transcendence of the Ego)
Descartes did not challenge Aristotle's category theory, i.e. the division of all entities into substances, essential properties (attributes) and accidental properties (modes). But he strayed from Aristotle's metaphysics in many other ways. For example, concerning which entities were the substances.
Sartre is usually thought to be following in Heidegger's footsteps, not the other way around. Heidegger
held a principle similar to "existence precedes essence", but he resisted Sartre's interpretation that existentialism was therefore "humanist" i.e. human-individual-centered.