Born the son of Provo Featherstone Wallis, a clerk at the Royal Navy's Halifax Naval Yard, and Elizabeth Wallis (née Lawlor), Wallis benefited from his father's desire to secure a naval career for his son: knowing the rules for officers' entry into the navy, his father managed to get him officially registered in May 1795 as an able seaman on the 36-gun frigate HMS "Oiseau" at the age of four, by convincing her captain, Robert Murray to list him on the ship's books as an able seaman.