The rule is in place only in Xinjiang which has a large population of Uighurs who are Muslims. The existence of the order was revealed by Radio Free Asia.
Xinjiang has a history of social unrest with mass-scale riots taking place eight years ago.
The app in question, known as Jingwang, apparently searches mobile devices for files that match those on an official blacklist.
Chinese authorities are reportedly checking people at checkpoints to see if they have installed the application as they were ordered to.
According to a report in Infosecurity Magazine, a group of Kazakh women were arrested after their conversations on WeChat, a popular Chinese messaging platform, were monitored and deemed illegal.
China regularly cracks down on Internet freedoms, with one of the latest orders being a January fiat to make all VPNs not approved by the government illegal.
Xinjiang authorities have reportedly told all citizens and business owners to provide their ID cards, mobile phones, external drives, laptops, and any media storage to local police for “registration and scanning” by 1 August.