Gefördert von seinem Onkel Johann Hartwig Ernst von Bernstorff trat er 1759 in den dänischen Staatsdienst ein. Zu Beginn seiner Karriere beschäftigte er sich vor allem mit Wirtschaft und war Mitglied des Kommerzkollegiums, dem sein Onkel vorstand, und unterstützte so Dänemarks positive Handelsbilanz.

Nach dem Tod von König Friedrich V. hatten beide Bernstorffs auch unter Christian VII. anfangs die führende Stellung im Staat. 1769 wurde Andreas Bernstorff zum Geheimrat befördert und gemeinsam mit seinem Onkel und seinem Vater in den Grafenstand erhoben. Doch schon 1770 verdrängte sie Johann Friedrich von Struensee. Nach dessen Sturz und dem Tod seines Onkels kehrte Andreas Bernstorff auf seine Stellung im Finanzkollegium zurück. 1773 wurde er Nachfolger seines Onkels als Staatsminister des Äußeren und – auf Druck der schleswig-holsteinischen Ritterschaft und gegen den Widerstand des Kopenhagener Hofs – Leiter der Deutschen Kanzlei, der zentralen Behörde für die Herzogtümer Schleswig und Holstein. Diese Position hatte Bernstorff zunächst bis 1780 und dann von 1784 bis 1797 inne.

Einen großen Verdienst erwarb sich Bernstorff dadurch, dass er die schon von seinem Onkel begonnenen Verhandlungen mit Russland über den Austausch des Gottorpschen Anteils an Holstein gegen Oldenburg und Delmenhorst im Vertrag von Zarskoje Selo von 1773 zum gewünschten Ende führen konnte. Während des englisch-französisch-spanischen Seekriegs im Zusammenhang mit dem Amerikanischen Unabhängigkeitskrieg brachte er, in Verbindung mit Russland, Schweden und Preußen, die bewaffnete Neutralität zustande, welcher Dänemark während verderblicher Kriege zwischen anderen Völkern einen langjährigen Frieden verdankte.

Aber infolge von Differenzen mit der verwitweten Königin Juliane und deren Minister Ove Høegh-Guldberg, der die dänische Hofpartei durch ein Indigenat-Gesetz, das Dänischstämmige bevorteilen sollte, stärken wollte, legte Bernstorff 1780 sein Amt nieder und zog sich auf das Familiengut Dreilützow in Mecklenburg zurück. Sobald jedoch der junge Kronprinz Friedrich VI. 1784 eine Änderung des Staatsrats durchgesetzt und den Einfluss der Königin gebrochen hatte, wurde Bernstorff zurückgerufen und in alle seine Ämter und Würden wieder eingesetzt. Von da an blieb er bis zu seinem Tod der leitende Mittelpunkt der äußeren und inneren Verwaltung und erhob Dänemark unter den schwierigsten Verhältnissen zu einer hohen Blüte. Den unvermeidlichen Krieg mit Schweden, zu dem das Bündnis mit Russland zwang, wusste er nach nur einer Schlacht schnell zu beendigen. Dänemark trat durch Bernstorffs Veranstaltung 1791 sogar mit dem glücklichsten Erfolg als Vermittler zwischen Russland und England im Türkenkrieg auf. 1792 lehnte er eine Einladung der gegen Frankreich alliierten Mächte Österreich, Preußen und Sardinien-Piemont zur Teilnahme am Krieg gegen die Republik ab. Auch später trat er Koalitionen gegen Frankreich nicht bei.

Durch dieses Friedens- und Neutralitätssystem sowie durch wahrhaft wohltätige, alle Gegenstände der Administration, Finanzen, Handel, Schifffahrt, Manufaktur- und Fabrikwesen sowie militärische Angelegenheiten betreffende Maßregeln wurde Bernstorff der Wohltäter Dänemarks. Ihm ist besonders die Befreiung des Bauernstandes in Dänemark von persönlichen und wirtschaftlichen Fesseln zu danken. Auch an der Aufhebung der Leibeigenschaft in Schleswig-Holstein hatte er einen bedeutenden Anteil, obwohl sie erst nach seinem Tod erfolgte. Dabei war er im Sinne der Aufklärung ein standhafter Verteidiger liberaler Regierungsprinzipien und erklärte sich stets entschieden gegen jede Beschränkung der Pressefreiheit. Bernstorffs Privatcharakter erscheint überall in dem günstigsten Licht.