On 29 Jun 1940, the HMAS Parramatta (L 44) (LtCdr Jefferson H. Walker MVO RAN) sailed from Fremantle to the Red Sea Force, arriving at the end of July. She spent the next nine months with escorting, patrolling and minesweeping and in April 1941 took part in the operations against Italian Eritrea. She towed the HMS Capetown (D 88) from Eritrea to Port Sudan after she had been torpedoed and damaged by the Italian motor torpedo boat MAS-213 (Lt.z.S. Valenza) during the night of 6/7 April.

In May 1941, the sloop was transferred to the Mediterranean Station, first based in Port Tewfik and after 3 June in Alexandria from where she operated as escort in support of the campaign in Libya. Her first run was made on 15 June, carrying a naval port party to Mersa Matruh and was followed on 22 June by the first run to the besieged Tobruk, escorting together with HMS Auckland (L 61) the Pass of Balmaha, which carried a cargo of petrol. On 24 June, the ships were attacked in rolling attacks by German and Italian bombers, which sank the HMS Auckland (L 61) and damaged the merchant. At dusk, HMAS Parramatta (L 44) picked up 164 survivors and brought them to Alexandria, while HMAS Waterhen (D 22) and HMAS Vendetta (D 69) first screened the rescue operations and the first then took the merchant in tow for Tobruk, while the second served as escort.

On her next run, the HMAS Parramatta (L 44) was en route to Mersa Matruh, when she was attacked at 05.45 hours on 27 Jun 1941 by the Italian submarine Jantina (Politi), which reported a destroyer of the Hero-class damaged in 31°34N/27°28E. But in fact, the torpedo ran too deep and passed underneath the vessel. From Mersa Matruh, the sloop went to Tobruk to escort the Pass of Balmaha back to Alexandria, where they arrived on 30 June.
After making good defects until 18 July, she operated until the end of the month as escort for the reinforcement of Cyprus. In September 1941, the ship operated as duty sloop at Attaka in the Suez Canal zone and in October on survey work in the Gulf of Suez.

On 18 Nov 1941, the HMAS Parramatta (L 44) and HMAS Yarra (L 77) left Alexandria escorting a slow convoy to Tobruk. They arrived without loss in spite of enemy attacks and returned safely to Alexandria on 23 November. 

On 25 Nov 1941 the HMAS Parramatta (L 44) and HMS Avon Vale (L 06) left Alexandria escorting the ammunition ship Hanne to Tobruk. About midnight on 26 November the ships were about 25 miles north of Bardia, in a pitch dark and raining night. The merchant was confused about her route into Tobruk and the sloop came alongside to hail the route by megaphone. While they steamed at about three knots, U-559 fired at 00.12 hours a spread of three torpedoes from a distance of 2000 metres at the merchant and the escort, but missed. At 00.46 hours, another torpedo was fired from a distance of 1500 metres at the escort, which broke in two after the hit and immediately sank.

The HMAS Parramatta (L 44) (LtCdr Jefferson H. Walker MVO RAN) was hit amidships by the torpedo, which caused a explosion in the magazine. The ship was torn apart, rapidly rolled to starboard and sank. About 30 survivors, including two officers clung to a raft that floated between debris. Two seamen saw a shadow in the distance and decided to take a chance and swim towards it. After three quarters of a mile and near exhaustion they were picked up at 03.05 hours by HMS Avon Vale (L 06), which already had rescued 19 survivors from wreckage. She then searched a wide area for the raft and other survivors, but the search was fruitless. However, three other survivors landed at the Libyan coast and were rescued by British troops. 138 men lost their lives, including all officers.