Marquet painted The Bay of Algiers during his second trip to Algeria, when he stayed at the Royal Hotel in Algiers from January to March, 1921. As he explored the heights of the city, he discovered picturesque views looking out over the harbour and the hillside gardens. Marquet set up his easel in the Mustapha Supérieur district, formerly a suburb just outside of Algiers, where he painted sweeping views of the bay from a foreground filled with bright flower beds punctuated with green cypress trees. These highly colourful artworks drew the curiosity of local art enthusiasts, whom the artist happily received in his home.

It was a time of travels and artistic fulfillment. His landscapes were harmonious, balanced, at once synthetic and naturalistic, bathed in the soft Mediterranean light. In March 1921, Marquet left the Algerian capital temporarily to travel to the oasis with painter Jean Launois and Marcelle Martinet, who would become his wife two years later. The couple would then return regularly to winter in Algeria, before settling there permanently during the Second World War.
 
Olivier Senn purchased The Bay of Algiers from the art dealer Druet on September 20, 1921, along with two other paintings, Herblay, Autumn and Women of Algiers. Particularly fond of the bright and colourful North African landscapes, Senn acquired another painting from the series two years later, Sidi-Bou-Saïd Interior painted in 1923. It joined the MuMa collection with the Hélène Senn-Foulds donation in 2005.