A firewall already prevents Iranians from accessing many Western sites.
The latest move coincides with protests throughout the Muslim world – including some in Tehran – against an anti-Islamic film posted on Google’s video-sharing site YouTube.
A government deputy minister announced the ban on Sunday on state television.
“Google and Gmail will be filtered nationwide, and will remain filtered until further notice,” said an adviser to Iran’s public prosecutor’s office Abdul Samad Khoramabadi.
The announcement was also sent out as a text message on mobile phones.
The unsecured version of the search engine, which is much easier to eavesdrop on, remains accessible.
The BBC Persian service says: “Google search website is accessible, but is not functioning properly. Google services which need a secure SSL [Secure Sockets Layer] connection are out of reach in Iran.
“Any attempt to get access to those services leads the user to a never-ending waiting phase, where nothing comes up.”
Users can only access Gmail accounts by using virtual private networks (VPNs), which allow web surfing behind heavily encrypted firewalls.
Many Iranians already use VPNs to bypass the government’s restrictions on other blocked Western websites, said Mahmood Tajali Mehr, an Iranian telecommunications consultant living in Germany.
“This is just a move by the Iranian governement towards a so-called nationwide intranet, to control all the traffic from the outside, and authorities are saying they will implement it in about three years.
“But every schoolchild knows how to bypass restrictions by using VPNs, it’s very common in Iran.”
It is not the first time Iranian authorities have cut access to Google services.
Both Google Search and Gmail were restricted in February, ahead of parliamentary elections in March.
Mr Mehr said that he did not think the services were going to stay restricted for long.
“This is just a propaganda tool to demonstrate that Iran is doing something against the US, but it is unlikely to last longer than a few days.
“The current trouble with the anti-Islamic film is helping the government with this propaganda.
“The state is saying that the people are asking to block these services because of the film, but there haven’t been such protests as in Pakistan and elsewhere, only small organised protests, so my personal feeling is that it has nothing to do with the film.
“Especially keeping in mind that YouTube has been blocked for some time already.”
Google’s YouTube site has been censored since mid-2009, following protests and allegations of vote fraud after the re-election of President Mahmoud Ahmadinejad.
The websites of several Western media organisations such as the Guardian, BBC and CNN are also blocked in the country, and a number of other web services, including Facebook and Twitter, are often censored.
In March, Iran’s Supreme Leader, Ayatollah Ali Khamenei, ordered officials to set up a body tasked with defining policy and co-ordinating decisions regarding the internet, called the Supreme Council of Virtual Space.
Despite the government claiming that the people had requested the censorship, many told the BBC they were outraged by the ban.
The BBC’s Persian Service said that the country’s Twitter users were protesting, and “even mocking” the decision, with some expressing concern about this being “a preliminary step towards setting up a national intranet”.
“This is a pre-determined scenario to block Google in Iran, they wanted to do this since long time ago,” tweeted one user, Hadi Khezriyan.
“Now they have found the best alibi to do it.”
Another Twitter user, Mnesfahani, wrote: “Students and businesses use Google services the most. This self-proclaimed superpower is afraid of satellites, internet and people’s consciousness.”
However, some Iranians seem to agree with the ban.
“Google has removed the name of Persian Gulf from its map and has banned users inside Iran to access many of its services because of sanctions,” Faramarz from Qazvin wrote in a comment to the same story.
“Banning the service will bring some losses to Google, although not substantial. I agree with banning it.”
Another BBC reader, Amir from Karaj, said: “It is OK, because people should not have access to these insulting films.”