The app, Survival Island 3 - Australia Story, tells users that they have to find ways to stay alive in "one of the most dangerous places in the world", including having to "fight with aboriginals - you invaded their home!".
The change.org petition, which has been signed by more than 65,000 people since it was set up on Friday, called for the app to be pulled from mobile stores, adding that "killing indigenous Australians is not a game".
"Selling games that promote racism and negative stereotypes of indigenous Australians is not acceptable," the petition added.
One petitioner commented that the game was "abominable", adding that it was "beyond racist".
By mid-day on Saturday, the app had been pulled from the two dominant smartphone app stores - Apple's iTunes store as well as Google Play.
A spokeswoman for tech giant Google, which offers apps through Google Play on its Android mobile platforms, would not comment on the game but said the tech giant would remove "applications that violate our policies".
Good to hear this is no longer available via Apple's App Store but dismaying it got through in the first place https://t.co/7OeKU54cDIโ Tim Soutphommasane (@timsout) January 16, 2016
Apple did not immediately respond to requests for comment, and the game's developer could not be immediately reached for comment.
Australia's Race Discrimination Commissioner Tim Soutphommasane wrote on Twitter that it was "unacceptable to see such promotion of violence and hatred against Aboriginal people".
Bianca Jagger, human rights activist and former wife of Mick Jagger, also tweeted that she was shocked by the "despicable" app.
Killing #Aborigines is a crime and it should be condemned by everyone. Ban this despicable #NIL Entertainment app https://t.co/lIlKVTXD1x โ Bianca Jagger (@BiancaJagger) January 15, 2016
Aborigines, the most disadvantaged Australians, are believed to have numbered around one million at the time of British settlement.
There are now just 470,000 out of a total Australian population of 23 million, and they suffer disproportionate levels of disease, imprisonment and social problems as well as significantly lower education, employment and life expectancy.
Source: Agence France-Presse
you get to play as a native (Koori, Native American, Eskimo, Maori, Zulu, etc...) and are armed with sticks, rocks, spears and arrows and have to kill wave after wave of white settlers who are armed with guns, diseases, cannon, and betrayals.
Level one would see you start with 50 lives (your tribe) and a target of 10,000 european invaders to kill before you pass on to level 2, where you start with 5 lives and 25% health (due to smallpox) and your target to pass the level is to kill 20,000 soldiers (but for every soldier killed, 10 more are added to the game.)
Level 3: Bonus Game! Guess which of these 5 sealed treaties will be honored! (none of them)
Level 4 sees you in a reservation and the challenge is to find food and work that isn't there.