The biggest threat posed by Yxes.A, also known as "Sexy View", is that it can spread through malicious links in text messages.
This creates a bridge between mobile phones and the internet, which means mobile botnets may not be far away, said Fortinet.
Mobile threats are likely to be a recurring theme, said Derek Manky, project manager for cyber security and threat research at Fortinet.
"We are just starting to see the tip of the iceberg with Sexy View, but we predict much more to come with the growth of mobile platforms, applications and broader bandwidth," he said.
Sexy View propagates by sending text messages to contacts on the infected mobile phone that contain a link to a server controlled by cyber-criminals.
The worm targets mobiles running SymbianOS S60 3rd Edition. It may kill some processes, but its main aim is to gather information.
The information, such as the serial number of the mobile, is posted to the remote server, but it is not yet known how that information is exploited.
The worm is spreading in the wild and executes on Nokia 3250 handsets, but is not limited to this, said Fortinet.