Sachverhalt: A. Die A._ Holding AG und ihre Tochtergesellschaften Ab._ AG und B._ AG (nachfolgend zusammengefasst: A._-Gruppe) betätigten sich während mehrerer Jahre in der Personalvermittlung. Ende 2001 waren sie überschuldet. Im Juli respektive August 2002 wurde über die Gesellschaften der Konkurs eröffnet, und die Gläubiger erlitten einen Verlust in der Höhe von rund Fr. 21 Mio. X._ war im Verwaltungsrat der drei Gesellschaften. Ihm wird zur Last gelegt, den Konkursrichter verspätet benachrichtigt und dadurch die ihm obliegende Anzeigepflicht im Sinne von Art. 725 Abs. 2 OR verletzt zu haben. B. Das Kantonsgericht St. Gallen sprach X._ mit Entscheid vom 12. Februar 2009 zweitinstanzlich schuldig der mehrfachen Misswirtschaft. Es verurteilte ihn zu einer bedingten Geldstrafe von 35 Tagessätzen à Fr. 80.-- bei einer Probezeit von zwei Jahren. C. X._ führt Beschwerde in Strafsachen. Er beantragt, er sei vom Vorwurf der mehrfachen Misswirtschaft freizusprechen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. D. Die Staatsanwaltschaft des Kantons St. Gallen schliesst in ihren Vernehmlassungen vom 12. August 2009 und 5. November 2009 auf Abweisung der Beschwerde. Das Kantonsgericht St. Gallen hat auf Vernehmlassung verzichtet.