I have just received a message from an Android app on my phone saying my phone has been infected with a virus and to click a link to fix the problem.
I'm not sure I trust this, is it possible to have a virus on Android?
It is possible to have malware on Android, although these usually 'infect' a device through downloading and installing apps from un-reputable and/or warez sites. When installing any app you should review the permissions and not blindly download/install an app simply because it looks ok.
It is possible that the message you received is from a malicious app or an app trying to get you to install malware. You can install a security app such as Lookout or Avast and they will scan your device for issues/malware. Be aware that anti-malware apps such as these can report false positives, and they may not detect all issues so you need to use common sense and ensure you only install apps you trust.
Thanks to t0mm13b for pointers on how to improve this answer.
In addition to the possibility that bmdixon raised of malware, I'd like to add that it's entirely possible that it's not even necessarily malware, but rather instead social engineering type adware trying to get you to install malware or buy something useless. You often see those types of pop up messages on websites for Windows users, and this sounds very similar to me. Without more info, like which app popped up this message or a screenshot, this would be my guess as to what's happening on your phone.
Many of these types of adware can be blocked using system-level adblockers such as AdAway, which can be installed from repositories such as F-Droid if you have root. (such blockers are no longer available on Google Play as they undermine Google's primary business model) Or of course by not installing apps that rely on ad revenue in begin with :)
If that application which sends that message is a trustworthy anti-virus you personally choose and installed, then you can trust the message.
Otherwise I recommend to ignore that message and uninstall the application which sends that message.
Internet is full of such false "free antivirus check"s, which push you to click on install their crap - but actually, this programs will install a backdoor, spyware or other crap. This exist on PC, now you met it on your android.
You likely have an instance of "rogue security software". Despite the name, it only pretends to be security software. From Wikipedia:
Rogue security software is a FraudTool (a form of Internet fraud using computer malware) that deceives or misleads users into paying money for fake or simulated removal of malware (so is a form of ransomware)—or it claims to get rid of malware, but instead introduces malware to the computer.
Unless this message is coming from a tool that you know and trust to reliably treat malware infections, do not follow the link, and remove the software, if you can. If the software came from the Google Play store, report it for investigation.
Android apps that pose as legitimate apps and warn you of such malware and provide a link to help you clear the virus ARE THE ONES THAT ACTUALLY INSTALL MALWARE.
I recommend that you do the following: