Andoria is an ice moon with mid-summer temps of -28° (assuming Celsius?). They seem to survive only via technological adaptation. Did they originate on another planet/moon? How could they evolve on this ice world? Was it previously more temperate? Is there an in-universe explanation?
Well, no - the Andorians aren't from the planet. They originated on an ice moon of Andoria.
The best evidence I can think of that they originated from that system would be the Aenar. They're a sub-species that diverged from Andorians long, long ago, and are naturally blind. Andorians long believed them to be a myth, until they made contact in 2104.
Otherwise, the Andorian first contact with the Vulcans would be my best guess: The Vulcans had their own version of the Prime Directive for centuries, and did not contact the Andorians until the 1900s. This strongly implies that the Andorians didn't have spacefaring technology until about that point, so they'd have to originate on Andoria.