Ill-health forced Brenton to relinquish his position on "Sibyl" and return ashore at the end of 1795. After a short period of convalescence, Brenton wrote to Admiralty requesting a return to active service. However, he was dismayed to learn that he had been appointed second lieutenant on a store ship, HMS "Alliance", a position he described as "disgraceful and degrading to an officer, who had been for some time first lieutenant of a frigate". His protests were dismissed by the Admiralty and in March 1796, "Alliance" set sail with a large convoy headed for the Mediterranean. Arriving off Corsica later that year, Brenton wrote to the Commander-in-Chief of the Mediterranean Fleet, Admiral Sir John Jervis, to appeal for a more favourable appointment. Jervis was sympathetic with Brenton's plight and installed him as first lieutenant on the 80-gun third-rate HMS "Gibraltar" which was part of a squadron undertaking a close blockade of Toulon during the summer of 1796.