He served on the ship-of-the-line Oldenborg in the Danish squadron off Algiers in 1746 [5][Note 1] and three years later as a senior lieutenant in command of the galley Achilles.

A series of reports sent by him to Copenhagen dealt with the Spanish seizure and plundering of a smaller royal ship which had called at Puerto Rico for fresh water.

He was further promoted in 1767 and in command of the ship-of-the-line Prinsesse Wilhelmine Caroline in 1771[2] when this ship was sent to reinforce the Danish squadron (under Counter-Admiral Hooglant[Note 3]) in the Mediterranean during the Danish–Algerian War.

On 30 January 1772 in Gibraltar harbour during a severe winter storm his ship dragged its anchor, colliding with the bow of HMS Trident before running aground.

[1] In 1774 and 1775 Bille was in command of the ships laid up but ready for active service in Trosvig, Fredrikstad from where he delivered ship-of-the-line Neptunus to Copenhagen.