Use large swaths of solid low-ish contrast colours to create the background. You can have more contrast in areas that are away from the creature, but avoid high contrast that's adjacent to the creature, as the details will clash.
Consider using diagonals in the background. Diagonals are largely absent from the creature, so they should help increase the contrast between it and the background. If you stick to just 45-degree diagonals, it should even fit the style.