Convexity for the max-plus algebra has been studied from different directions including discrete geometry, scheduling, computational complexity. As there is no inverse for the max-operation, this used to rely on an implicit non-negativity assumption. We remove this restriction by introducing `signed tropical convexity'. This allows to exhibit new phenomena at the interplay between computational complexity and geometry. We obtain several structural theorems including a new Farkas lemma and a Minkowski-Weyl theorem for polytopes over the signed tropical numbers. Our notion has several natural formulations in terms of balance relations, polytopes over Puiseux series and hyperoperations.