Paid my dues is een single van Anastacia. Het was de eerste single, die afkomstig was van haar albumFreak of nature. Anastacia scoorde er een wereldwijde hit mee, behalve in thuisland de Verenigde Staten. Er verscheen verschillende versies van deze cd-single.
Het nummer is opgenomen in New York City, in de Cove City Sound Studio en in de Sony Music Studios. De bijbehorende videoclip is echter opgenomen in Los Angeles, een stad die haar veel heeft gebracht, maar waar ze ook een keer in neergeslagen ('I’ve been knocked down'). Anastacia heeft haar succes door schade en schande verdiend en laat zich er niet door van de wijs brengen. De video werd geregisseerd door Liz Friedlander.