Sterett's first assignment was as Third Lieutenant of the USF Constellation, under Captain Thomas Truxtun, which was sent to do battle with French vessels during the Quasi-War. Sterett was commanding a gun battery when Constellation attained the first-ever U.S. victory against a foreign navy, defeating and capturing the French frigate L'Insurgente on 9 February 1799. L'Insurgente lost 29 dead and 41 wounded; the only American loss was a man run through by Lieutenant Sterett's saber.
During the battle, a Seaman, Neal Harvey, was summarily executed by Lieutenant Sterett after having abandoned his post in a panic. Upon Constellation's arrival back in Baltimore, the anti-federalist press, who opposed the military in general and the Quasi-War in particular, seized upon this incident as an example of the arrogance and cold-bloodedness of the Navy. The objections intensified when Sterett was heard to say, "We put men to death for even looking pale on this ship." The Navy saw things quite differently, and soon promoted Sterett to the rank of First Lieutenant.
A year later, Sterett was involved in a battle to a draw with the 54-gun French frigate Vengance. Soon afterward, he took command of the schooner USS Enterprise where he remained through the end of the Quasi-War, capturing the privateer L'Amour de la Patrie on 24 December 1800.
After resupplying in Baltimore, Sterett sailed Enterprise to the Barbary Coast in June, 1801 as part of a force under Commodore Richard Dale, in the first stages of the Barbary Wars.
On 1 August 1801, Enterprise under Sterett's command handily defeated the 14-gun Tripoli, a Tripolitan corsair. After twice faking surrender, Tripoli suffered 30 dead and 30 wounded, including the Captain, Rais Mahomet Rous, and the first officer. Enterprise suffered no casualties.
Since there was no formal declaration of war, Enterprise was under orders not to take prizes. After her crew was ordered to dump its guns overboard, Tripoli was allowed to sail home, where her captain was humiliated and punished.
Enterprise was sent back to Baltimore with dispatches after this engagement. While there, on the recommendation of Congress, Sterett was presented by President Thomas Jefferson with a sword in gratitude of the victory over the Tripoli. Enterprise's crew was also rewarded with an extra month's pay. The ship returned to the Mediterranean in November, 1802.
Sterett turned over command of the Enterprise to Stephen Decatur in April, 1803. He was then promoted to master-commandant and offered the command of a brig which was under construction.
Sterett had been senior in rank to Decatur, but due to their comparative service as of 1803, Decatur was selected to be promoted above Sterett. Sterett therefore resigned from the Navy on 29 June 1805 to join the merchant marine. He died in Lima, Peru at the age of twenty-nine.
Andrew Sterett has had three ships of the United States Navy named in his honor, for which see USS Sterett.