There is a letter from Fermat to Mersenne, sent in September 1636, where Fermat proposes such problem:
$3^o$. Invenire duo quadratoquadratos quorum summa aequetur quadratoquadrato, aut duos cubos quorum summa sit cubus.
or "Find two fourth powers, whose sum is the fourth power or two cubes, whose sum is a cube."
So, Fermat definitely had thought about this problem in 1636. The letter could be found here.